ZK HACK - Aleo Workshop Part 1, Deriving value from zkSNARKs: an example with ZEXE

Transcript

arrow asked me to to kind of be up and help him moderate some questions uh errol if you still want me to do that i'm happy to be on by the way hi everybody from the community uh and and from the zk hack community who joined today really excited to share a little bit more about elio and leo uh courtesy of errol but uh thanks a lot anna for giving us the opportunity to speak here absolutely yeah i want to just get your screen up because then we can kick off and i'll bounce off one second entire screen there we go uh so thank you all for joining and thanks for coming up as well alex i hopefully there'll be some questions in the chat and i won't be able to monitor the chat so alex is just

i'll interrupt you i'll let you know if someone asking is asking a question yeah i ideally not for well maybe every question but if it's a bit more important ideally we can answer them in the chat but i'll leave it up to you sounds good thanks okay so welcome to this week's zk hack we are elio and we are trying to make private applications possible and i'm going to go over what that means just quickly my name is errol drummond and i am head of education at elio and two compiler engineers help me prepare some of the contents for these slides and they are dimir shiminayev and pranav gadamadugu i want to take you on a bit of a journey

there's three main things i want to cover in the first part i want to go over how we can derive value from snarks i don't want you to worry about how they work i want you to see why we should care about them and what we can use them for to derive for us to derive value i'm going to do that with an example called sexy which is a blockchain design that we are implementing in the second part i want to talk about compilers the why in the what if you went to the the first zk hack you may have seen circum2 from ident 3 you may have seen cairo from stark where we have leo

but in a lot of the stuff i've seen it kind of assumes that you know why we're making compilers and what they're for so i want to cover why we're doing it and why they're valuable and as a result when you should be using them and in the third part i want to do a little play around with leo where we're going to make a game of hangman so i can show you that we can do more on chain than just send each other tokens and without further ado we can get into the first part um just so we're all on the same page snarks are in the realm of verifiable computation now this just means

how do you check that a computer program has been done correctly now there's a simple way to check if a computer program has been done correctly you can just redo it if you redo the computation and get the same result you'll be happy that it was done in a valid manner every single blockchain needs verifiable computation this is a shared ledger and we want to make sure everyone interacts with it in a valid way so bitcoin and ethereum they do it directly if you want to chug a computation onto bitcoin or ethereum chains the on chain you just verify the computation by redoing it

but there's a new technology now and it's called a snark a zk snark i've got a little image for you here generally speaking you have your computation the thing you want to prove you have some public data and you have some private data that you're going to keep to yourself you're going to make a proof of this computation and it's not a coincidence that the proof is much smaller than the computation and you can send the proof to a verifier and a verifier can check whether what you did was valid or not using the same public data there's four main things you should know about the snark the first is that verification of the proof is exponentially quicker

than redoing the whole computation one analogy is that if you want to check that i did a sudoku correctly and i send it to you you're not gonna you're not gonna get the starting sudoku and fill it out step by step work out everything and then compare it to my result there's a lot of redundant computation in there you can simply look at the result and see whether it is correct or not so snarks allow you to verify stuff much more quickly than redoing the whole computation the second main thing is that the proof size is also exponentially smaller

in the sudoku example i don't need to send you or you don't need to send me every logical step you use to get from the start to the end you know there's a one in in these boxes in those places and when you line it up it means a one can only go here in this other box like all that's redundant you just need the end result and you can check it directly so much quicker verification exponentially smaller proof and the data can be kept private it can be kept secret the the sudoku analogy here doesn't really work it falls apart because you can prove that you know the solution to a sudoku puzzle without showing me any of it

um if you look on wikipedia for zero knowledge proofs there's a great example with where's wally where you've got to find the little guy in the book and lastly the function is publicly known so if you're proving to me that you know the solution to a sudoku puzzle i need to know that it is a sudoku puzzle it's not a crossword it's not a karuko you're not sending an nft you're proving uh that you know the solution to a sudoku puzzle i need to know that and these are the kind of four fundamental properties of a snark you don't need to know any of the details these are the important parts if you want to be building things of value and then i have this here that do we

always maintain the zero knowledge of the data i wanted to emphasize this because a lot of times that we use a snark people give up the zero knowledge property the reason we do that is that on a blockchain if you want to prevent a double spend it's hard to prevent a double spend whilst maintaining zero knowledge of the data the simple solution is just show the data you know you don't do a private transaction you can send bitcoin but make it public and that way it's safe and that way you get the scaling properties but you don't get the privacy yeah so don't make the assumption that because somebody is using as okay snark

that they'll have data privacy and how are snarks being used uh i want to show you that the value derives from how we use them uh most teams are using just for scaling we're trying to do privacy as well to enable private applications and i i put wood on the slide because snarks are is are a fundamental building block in the same way that wood is wood doesn't inherently have any value really but we derive value from how we use it you can build a chair you can build a house

you can burn it you can make paper from it and depending on what your problem is you want to do something different if people are cold you might want to burn the wood or build a house if people keep forgetting things you might want to make them some paper and a snark is the same thing it's just a fundamental tool that you can use to derive value somewhere else now when we talk about applying a technology to derive more value there's some kind of implication that there's a limitation that we can't quite do as much as we want and this is inherent when you design a blockchain in the beginning you say we

want it to do these things and this is what we did for bitcoin ethereum and it went really well and and then we're like oh we can do all those things and actually it's getting a bit crowded here we we we've proven the concept and that we can do it but now we need to do a bit more we need to maybe add some more functionality or allow more people to use it and if we want to achieve these new things we have to redesign the blockchain a little bit or add functionality on top and i want to point out that the three key limitations that we are aiming to tackle the first big limitation that we know of is scalability so all miners are re-executing the entire computation to ensure

valid execution we're sharing a limited resource and if each transaction takes up a big amount of space it limits how much we can do moreover we have these growing chain sizes and like the growing chain sizes aren't unreasonable it's not that we can't deal with them it just causes some problems and it would be a lot more straightforward if we didn't have those issues but we also still have limited throughput and this is kind of like in the development of computers when we were time sharing there weren't in the past personal computers it would usually be a university that had a computer and you

could go to university and apply to use it for some limited amount of time to do something very specific you can't really be creative or innovate with a tool if you don't get to play around with it you know it's hard to know what to do with it if you can only use it for very important things and right now the blockchains are don't have the scalability so we'll only use them you know spend 70 dollars to make a transaction on ethereum it's quite a high barrier to entry for creativity and how do we get to the next level the second large limitation and this is a really really big thing that we're focusing on

is the privacy now most chains are pseudonymous by default they're pseudonymous by default because the builders assumed that privacy was important but it turns out that pseudonymity is not as powerful as we thought it was there's growing evidence that the only people you should worry about can link your pseudonymous accounts to who you really are and as our digital footprint grows particularly our blockchain digital footprint we have to start thinking about these in more detail based on what will happen in the future so right now all the transactions are visible and there's a ton of metadata that can be found and used and i want to explore

this just a little bit more what does this mean for us personally well first off there's front running maybe you want to buy something online and you're going to buy it and you need to pay more then you should be paying because someone saw that you're trying to purchase something and they quickly bought it and raised the price and then sold it to you for the higher price and kept the difference and that's something that just well sucks right then we have facebook look at cambridge analytica harnessing tons of our data from facebook to make profiles about each of us and decide the easiest ways to influence us to control the outcome of a democratic election all these kind of

things that we should really be terrified about and ideally should be making impossible if the data wasn't available in the first place they it's not possible to to manipulate us in that way just punishing them afterwards means that it's still possible and that's not something we should really allow similarly for whatsapp i used to think maybe you did too that because my messages were encrypted that i was all good they didn't know anything about me it turns out there's a ton of metadata that whatsapp can use uh to yeah work out who you are they know how many people you message

they know what time you message them they know the frequency how often back and forth you message with people they know the length of the messages if you're messaging one person throughout the day deep into the night probably in love they can work out year off relationships with people they know the model of your phone how much it cost when you bought it because you logged into whatsapp straight away the language the time zone they can work out your rough socio-economic background now all this data and look how they're learning to weaponize it against us and if you cared about encrypting your message in the first place you probably care somewhat about the rest of this as well

all this other data now we have an assumption in the blockchain space an economic assumption it's a general assumption but we harness it a lot more and this is that you don't need to employ somebody to make something happen we don't employ people to mine blocks we just say hey if you do mine a block we'll give you a reward and if the economic incentive is large enough people go and do it so if somebody or some group can go out there and scrape all your metadata from these blockchains

process it sell it off to the highest bidder by our own assumptions somebody's going to do it at some point and it feels like maybe we should just make this impossible make these parasitic business models impossible and encourage companies to act more in our favor to not weaponize users data against them think about the history you're leaving on the blockchains you know oh you're sending money monthly to coinbase at this amount you probably make around this amount of money oh you missed a payment maybe you're having some problems oh you increased the size of your payment maybe you got a promotion oh you buy this very specific set of nfts

naruto naruto manga magic the gathering something what does that say about who you are and as we can start doing more on blockchains more nfts and music more ownership of things a car a watch uh a house if if all of that's publicly visible it could be linked to us how much influence are they gonna be able to have over us it also is quite relevant to businesses again they can also be front run they can have things cost more for them because they're probably whales and have a lot of capital

and they can be exploited in this moreover everything they do on a blockchain is going to be visible all their competitors will know what they're doing on a blockchain and how many resources they have and how they're spending them this is a ton of information and i i would be surprised if any business would be willing to put itself through in that scenario you know so this isn't just relevant to us but it's also really very relevant to businesses the last limitation that i want to touch on is limited application runtime so in practice on aetherium your computation can't take more than 0.1 seconds now this is enough to send

ethereum to send nfts and to do some other things but clearly you can't do everything and there's a ton of smart contracts or programs that we can't do on ethereum because of this time limit i mean we also have gas and the gas is to encourage a time limit but even if there wasn't gas on ethereum your computation like you can't make a new block until your computation is done so if you want 10 second block times on ethereum the maximum your computation could take is 10 seconds but even that's not possible because you have to send it to the network and there's other things that can be added and they have to make the block and all this stuff but there's just an upper limit on how long a

computation can be so that's a whole realm of potential programs that aren't currently possible this is also quite a new idea and there's a lot of innovating and creative people who need to be brought to the space to to make use of this new tool but one idea is that uh it's quite important for many businesses to buy and sell data whether this is patient data to do some processing and maybe work out things for research but with this possibility you could analyze your data and make a proof about the data that the data has certain properties maybe the age of the patients maybe what they're

suffering from and all this other kind of stuff and this way you can check that the data you're buying has certain properties that you wanted to have and prevent some problems there how do we gonna tackle the these issues that we're seeing there's two primary ways the first i say augment the layer one and by this i don't mean change the underlying layer one this is phenomenally difficult to do and we're seeing now with ethereum trying to switch to ethereum 2.0 for proof-of-stake and other things which i think is a really good idea but as far as blockchain design goes it's quite limited in the size of the

change and we're seeing a lot of problems of the sort where it's very hard to change the wheels on the bus when it's going at 80 miles an hour we got a theorem in motion send it on its way and adding all this community and technology and functionality and after a certain point changing the backbone of that is phenomenally difficult what i mean by augmented layer one is adding some functionality on top that uses a snark to try and tackle these problems building a successful layer one is really really difficult and so it makes sense to try and add this functionality on top of a chain

that's already made it there it's a great solution and we think it should certainly be pursued but the other main solution you can take and this is what we're trying to do is just by creating a new layer one snarks weren't possible in the past they weren't really possible when bitcoin ethereum were being designed starts were first invented or discovered in the i think 80s or 90s but even in 2015 proving the solution to a sudoku puzzle just took unreasonably long it wasn't a tool you could use it's only in the past few years as we made a lot of new technological developments in in the proof systems that they have become feasible to

integrate into a blockchain and we thought that it would make sense to design a blockchain around a snark rather than laying on top so this is sexy zero knowledge execution and this is the thing we're implementing at elio howard woo here is a co-founder and our ceo produced mishra is also a co-founder and is on the team so we've got two of the authors helping make this a possibility i now want to go over with you three key things within sexy to help you understand some of what's going on and how we're tackling these problems

the first is just the core idea of sexy what it's really mainly aiming at that you compute off chain and verify on chain the second is going to be how we prevent a double spend and the third is where we get functional privacy from and additional scaling which is through one layer recursion so now this is the core idea we want to do a computation make a proof of it and then we'll send our proof to the chain so the proof remember is much smaller and can just be verified on chain instead of doing the whole computation so here's your application execution this is your general circuit whether it's sending an nft or using some other

kind of smart contract program and it's going to take in some public data that's going to be visible to everyone and some private data that you don't want anybody to know it could be your secret key it could be uh you know the number of alia credits you have it could be anything else you want to maintain just for you you'll get out of proof and now it's this proof that you'll send to the network a node will receive it and they can check it and if it's valid they'll send it to the chain they'll get out true false they're also checking it with the same public data that you used yeah so you can make things public but ideally we want things private by

default and to make that a possibility and this is the core idea prove off chain send the proof to the chain rather than entire computation there's one more thing we need to make this work many snarks require some kind of randomness and you need to generate the randomness in a safe way to make the proving and verifying keys and we are in the process of doing that i think we've almost finished but uh just quickly we're doing something called a setup ceremony and provided one person involved in this setup ceremony is honest you can trust that the snark is going to

be safe so we do our setup ceremony and we got a proven key verifying key of course we use the proving key in making the proof and the verification key in verifying the proof [Music] so this is our setup we've had i think i took this yesterday at least 1900 people taking part which we believe is more well far more than the next largest we know of which was tornado cache around 1100 or 1400 and recall that as long as one person is honest the whole thing is safe so if you open this ceremony up to everybody online for anybody who wants to take part which is what we're all doing

and you get 1900 people i think if if you don't believe that there's a single honest person in 1900 online strangers then i don't know you must be so cynical that i can't convince you of anything the second main thing i want to show you is how we prevent a double spend recall i mentioned that if if you want to maintain data privacy you need a way to prevent a double spend and i'm going to show you how we achieve that in sexy it also required that we we make use of these things called records so a recorder if you know a utxo model like

bitcoin this is the same kind of thing this is a record with a certain number of alia credits in it and some other data that we can use so this record k has been added to this block beta and there's going to be a new block made called omega and we're going to want to do a transaction in there i'm going to take record k and i'm going to use it put it through some function whatever my application is and get out a new record record n and this is our transaction m i'm going to make a proof that all of this was done in a valid manner and alongside this proof is going to be a serial id you see this record k here

it has something called a commitment an id within it and i'm going to put this record through a very specific circuit and this circuit is deterministic so if i put record k through it i'm always going to get out the same result which is this serial id now hello errol if i could pause you one second there's a question in the chat um is this set up like z cash sorry going back to the setup a few minutes ago um the the setup ceremony i'm not a hundred percent sure on but this is preventing

the double spend this is the same as how z cash do it but zed caches do it for money and not applications yeah so i can i can actually quickly take it yeah so roughly the setup ceremony so this is a question from zahair i hope i'm pronouncing that right i'm sorry if i'm not um yeah the uh the setup ceremony is similar to uh how z cash this i think it was sapling ran uh ran it and that's uh using a protocol a multi-party computation protocol called powers of tau uh there are some different um something called optimistic pipelining and uh you know and have some other kind of kind of features to update that protocol um

if you're interested we have a blog post on our site and errol's actually written a great post on our brand new medium blog uh describing uh how setup so what certain setup ceremonies are how they work why they're important um so i can share in the in the chat here some of those resources so sorry arrow to interrupt i'll let you keep keep on no thank you very much alex i appreciate the the input um okay where were we so we made this proof and we have the serial id with it now we're all ready to send this to the chain as i showed you before so we can send the proof pi with the serial id to the network and if it's valid the nodes validate it and it gets added

to a new block and this record n is now in inside now in the future if you try to use record k again you will have to put it through the same circuit and you're going to get out the same serial id even if the context is different if it's in the future with a different function and you're using it with other records it doesn't matter you're still going to get out this same serial id now when you get that proof with that the same serial id and you send it to the network the the nodes who receive it will say hey we've seen this serial id before you're trying to spend a uh a spent

record this is invalid we're not adding your stuff to the chain and we prevent a double spend yeah and now we can maintain data privacy moreover there's something else happening here the serial id you can't see which commitment it came from you can't like undo the circuit and see what it started from which means that by looking at the serial id you don't know that it came from record k as far as you're concerned when you see this proof here you know that it used a record somewhere in the history anywhere in the history and that's all you will know

there we go we've prevented a double spend we've made our chain secure allowed ourselves to maintain data privacy and then the last bit of detail there's a few things going on here in the application execution and they're pretty important so i want to explore them a little bit more you'll have your general application this will be sending an nft sending bitcoin it could be playing a game of hangman whatever smart contract program you you've created on here this is your general application you will make a proof that you did this application correctly so pi is just maths notation for a proof and i've put a little m here

because this proof is made with the marlin proof system it's an r1cs proof system uh that we that we use alongside this proof we have a bunch of other proofs so these pi i the curly brackets here mean that this is a set you know this is like pi one pi two up to some number i think we have around 10 of these proofs here alex um errol sorry one other question from the chat from uh david wong hey david yeah he was a cereal i um i don't know if um if you have that detail you want to share that detail

uh pratush i think you're in the chat you can feel free and type in uh type it in as well i think up to you errol whatever you prefer i i think practice is going to be the best to answer this this is a lot more detailed and uh you can find some explainers by anthony mclaren as well i think go over this uh i can't say for sure the parts i remember is that i think you might need to use your your secret key to do some stuff i think i'll just leave it to practice to answer that clearly before i mislead people yeah i said it's fairly similar to how z cash nullifiers are derived it's protectious answer okay thanks uh right so we have all these other

proofs as well and this is record use and creation the birth predicates what this each record has birth predicates and death predicates and the birth critics say this record can only be made under these conditions similar for death predicates you can only spend this record under these conditions and this will be things like you can't make a leo credits out of thin air now you can't make other things out of thin air you know all the things all the requirements you need to ensure safe running of your program so we get all these proofs here now one of the key things here is that this paem this smiling proof in order to verify this proof you need to know

what this application was you need to know whether it was hangman or sending an nft or anything like that so whoever verifies this proof needs to know what this function was but i said that sexy achieves functional privacy as well and the way we do this is by verifying these proofs ourself and making a proof that we verified the previous proofs this is called one layer recursion because we're proving that we verified a proof so we of course the recursion is that you're putting a proof into verification and getting out a new proof and now in order to verify this proof you need to know what this application

was this one air recursion but this is a constant circuit it's a graph 16 circuit and everybody knows what this is but you no longer need to know what the general application was you can just keep this data private in this new circuit so we can kind of point out this is where we get functional privacy from moreover growth 16 is the fastest proof system we know of meaning that if you make a proof using graph 16 it's essentially going to be as small and as fast to verify as is possible so we're kind of doing two birds one stone here we're maximizing scaling of a

transaction and we're also achieving functional privacy oh okay thanks that was a lot of detail i hope you managed to hang on to a bunch of it and i want we want to look here now at how we're solving the limitations we we discussed earlier with the first imitation of scalability i just showed you that this extra this roll up or recursion you know squeezes it down as much as possible and in fact this proof is always the same size so we're making uh transactions on chain far far smaller uh allows us to have more transactions per block it allows uh the chain to be

smaller in data size and removing execution there's a lot of things we're doing here at the same time similarly for privacy i've shown you that we get functional privacy by default so you can hide what you're doing you can hide the data as well and we went over a few examples as to the importance of of all this privacy and that it's seemingly an essential thing that we want to have possible on a blockchain minor acceptable value it becomes much harder to achieve you know miners can't decide which transactions to put in a block based on what will reward them the most because as far as they can see all the transactions basically look the

same you know there's nothing for them to go off to to to achieve what they previously could but you can also enable a view key like if absolutely everything is invisible there's not really much you can do yeah so you can make things public when you want them to when you want them to be yeah but privacy by default and as an option limits application runtime now that we compute off chain and make a proof and send the proof to the chain it doesn't matter if your computation took a second a minute an hour a day you're still going to squeeze it down to a proof and just chuck it on when it's

ready you know provided you haven't used records that have been spent in that time it's all good you can run it for as long as you as you like and yeah this has just opened up a whole new paradigm in terms of what's possible and we're looking forward to people innovating and figuring out what we can do in terms of the ecosystem the kind of things that we're hoping or we're going to be building and looking forward to seeing in reality we can have a private nfc marketplace so again if you don't want everyone to see exactly your whole history of nft purchases um yeah you're gonna want a market like

this i'm just recalling you know when you're like 15 16 on facebook and you're liking all these weird pages and as you grow up you see you see these pages you liked and you're like oh that's embarrassing i better unlike that page so that people don't see the embarrassing things i did when i was younger well similar for the nfc marketplace there may be some things you want to keep to yourself so we need this to be a possibility there's a private data marketplace this is what i touched on earlier where you can prove properties about your data before buying or selling it on there the xero knowledge gaming i'm going to show you hangman

um but i mean there's no necessary reason why you do hang man on chain it's just a fun example but you can do poker for example and many other card games uh and other topics uh that it makes sense to actually put on chain you got on chain ai uh this is a thing where you can prove you have you know data that when processed through a certain ai outputs some results again a kind of new thing that we're exploring and then there's all this digital identity stuff there's a thing called verifiable credentials like like the kind of thing you can do with this is you could put your passport on chain

and and then you can use that and not reveal anything you don't want to like you know i'm british and turkish but i don't want to have to show people my passport with all my details of my name and date of birth to to do various things i'm not saying that we're going to have passports on chain in the short term you know maybe in the very long term it's going to be possible but there's more short-term goals in that respect it could be like a university you know i have a maths degree and a biochemistry degree from these universities and you'll be able to put that on there um another thing is in supply chain management if you think of your corona vaccine like where do the ingredients for the vaccine come from

in terms of the supply chain you can have everything be stamped where it was at certain times that these parts of the of the vaccine came from these labs produced under these conditions etc etc actually walmart did this very well a few years ago walmart had i think it was lettuce and there was some food poisoning everyone was getting really ill and they had to figure out which shops these letters came from and which farm it came from and the other shops the letters went to and i think in the end it took them over a week to work this out and i think they also had to just take all the letters off the shelves because it was too difficult

so what they did in response is they built their own private blockchain just for supply chain management so that the lettuce in the future when it goes it gets stamped everywhere on chain it was at this place at this time etc etc and now if they do want to work out the same thing where letters came from and the other shops it went to they could work it out in a few hours which means they could take it off the shelf within the day prevent other people getting ill prevent various problems and we're expanding blockchain use cases into that area like walmart did it themselves but if you're a smaller company you're just going to want to use a public blockchain but also you're

probably going to want to have privacy of your stuff there's also voting infrastructure blockchain turns out to be primarily a way to organize ourselves and decide how to make changes to things we're doing there are things called daos now decentralized autonomous organizations and they're kind of like companies that are doing things on chain but you're automating away some of the things that have to happen in order to do this you need voting infrastructure how to vote and it turns out we can be more creative than we used to be we have quadratic voting and a various other types and this is all the kind of stuff we're going to be building on a leo and

we're already moving in that direction we already have digital identity stuff and some verifiable credentials there's some games being made yeah and i also managed to design a decentralized voting system on alios and i mean in the sense that the tallying mechanism is done in a threshold manner so you could for example have a hundred people who we trust to tally our vote and say if at least 70 of you work together you'll be able to tally our vote uh and this way if you want the only way to bribe or or allow collusion is by bribing all 70 of the people involved in

that in the uh voting yeah so if you're really really worried about collusion or bribery maybe you'll want something like this okay thank you for taking part in the first part i hope you learned some things about how sexy works