ZK8: Demystifying Zero-Knowledge Programming – Howard Wu - Aleo

Transcript

foreign hi everyone I'm Howard um if you don't know me I'm a I'm a co-founder of elio and uh today I want to talk a little bit about programming in in zero knowledge and the programming model of zero knowledge I think there's been a lot of discussion especially over the past few years about building out you know ZK virtual machines and especially in light of the discussions recently with zkevms I thought it would be worthwhile and a good use of this opportunity to really talk about the challenges with respect to the account model some of the ways to remedy it and then more broadly speaking how to build tooling and infrastructure around that

um so to get started um a lot of the work that I'm going to be talking about today was actually born out of a research paper from several years ago called called sexy it was published in Oakland 2020 and introduced a protocol that extended the zero cache protocol or akz Cache to support general purpose applications um before I do do jump into things though I think that it's worthwhile especially because there's a lot of newcomers into this space to really go through how zero knowledge at a very basic level works and actually before I even do that I want to thank Anna for putting together this amazing Community it's been several years in the making and the good news is because not many people clap for zk1 when she was

checking I can reuse a few slides in here which will be also very helpful since uh I want to make sure everyone's on the same page about how zero knowledge works so what the what the concept of zero knowledge proofs is and fundamentally you know what are the assumptions the trust assumptions between the approver and the verify which we'll talk about next um so let's jump right into things in terms of the The Talk today the content is going to be broken into three parts um the main thing that I really want to convey is that there are things called ZK snarks uh my my hope is to help you understand on a on a higher level how things work there and then dive into the concept of a zkl1 and how you can build a virtual machine around around a blockchain that that can be provably

verifiable um and then lastly to get a little snarky and talk a little bit about about the way that we're instantiating things on a Leo so let's jump into it what are ZK snarks well to to even talk about that we need to start with a basic premise which is to say that cryptography is a really powerful tool for building secure systems and much of the cryptography that we use today is really to give security guarantees about data what do I mean by that well for one um when whenever you're transmitting uh information say over the web between two parties one of the things that you really want to do is encrypt your content so that only you at the center as the sender and the receiver see this message and so we use cryptography for

encryption the second way that it's commonly used today is really to offer security properties with respect to authentication and what I mean by that is that when you have the sender and receiver communicating with each other over the web you want to make sure that the receiver is really getting the message from the sender and so you know one way that you can do that is you sign the message and then send it over and and these are the the two primary mechanisms that we use cryptography it's really about securing data and data at rest really um but the question is can I can I use this type of cryptography to do even further to really give guarantees about computation and this is where the domain of cryptographic proofs comes into play cryptographic proofs can offer privacy

preserving uh guarantees for for computation and that's something that that's in my opinion a very new field a very new domain in terms of what's becoming practical and ready to use in the real world in particular a cryptographic proof is really saying hey like I securely computed this equation uh f of x and its result was Y and the goal is to convince other parties on the internet that I really did do this and when you dive in and double click there's an even further uh kind of specific segment of cryptographic proofs called zero knowledge proofs and zero knowledge proofs are a lot of there's a lot of jargon here so let's break it down the Privacy preserving

cryptographic proofs of computational integrity and this is really taking it one step further and what I'm really saying here is to say I know X such that y equals f of x where X itself is a private input and this takes that concept of a cryptographic proof and and kind of takes it one step further so when you're on the web sometimes you don't want to share everything that that you have or know especially when it comes to personal information pii across the web to other people as well but in order for other people to verify that you really ran you know this program and got this result why you know they need to somehow trust or believe that you use the right inputs and and if you don't want to reveal that then you know zero knowledge proof ends up becoming a very useful primitive for this

I think another way to frame a zero knowledge proof is to say in English that I know the secret I can't tell you the secret but I can prove to you that I know the secret and and this is this is really getting at the heart of of what what zero knowledge proofs are about it's really trying to convey information to another party without revealing the full set of information that you want to reveal so to give you a concrete example of it there is a very canonical example that many of you may have seen on the internet which is the world's Waldo problem and it says the question goes like this can you prove to me uh that you found Waldo without telling me where he is on the map um and you know you can take a moment to think about it I'll give a quick fun

anecdote which is to say that when in in in prison in creating these slides um I actually had to go find an image of where's Waldo and it took me quite a while on on Google search to find a good image of this because I had to keep checking whether the image itself had Waldo in it I wasn't sure if there would be a April Fool's prank in there or not so it would have been really nice if there was already a zero knowledge proof for it with the image so that I could just pick one that looks really visually nice but just to give the answer away um first off Waldo's like right there and the way that you want to show to another party that you found while though is really is really as follows you want to take a really big white

sheet of paper and cover the entire screen with it just the entire screen something that's just much larger than the map itself and you want to cut a little hole in that white piece of paper just enough to fit the size of Waldo so that when another person comes into the room and just sees a giant blank canvas with a little hole and sees Waldo sticking out they can be really convinced that there is Waldo on a map and Waldo truly exists and that you found Waldo then if you ask him to leave the room and you remove the white canvas when they come back into the room they just see the basic map again and they can now take a stab at it and that that's one way to kind of convince you that you know I really found Waldo Waldo exists on the map and I know where Waldo

is on the map without revealing where Waldo is relatively on the map Where is Waldo he's right there so yeah this is one canonical example and I'll very quickly run through just just another one which is the Alibaba cave which is also a classical one if you go to the Wikipedia page you'll find this one and credits to Wikipedia for the images too um but just to give you some background context this this example actually came from a paper back in 1989 called how to explain zero knowledge protocols to your children I'm not sure whose children are learning about zero knowledge troops but you know for them I say I applaud you and I'm very excited to work with you in

the future you guys are going to be Geniuses but but the basic premise goes like this you have Alice and Bob Alice is basically walking into a Cave the Cave has two sides Branch a and Branch b both branches are actually connected by a door on the back side there that's that black line and once Alice walks in Bob can flip a coin and say I want you to come out of say a if it's heads or or B if it's tails and if Alice has the key Alice should be able to walk right through that door in order to come out the appropriate side side so if Alice randomly said I'm going to go in path B and Bob says come out of path a well she should be able to open that door and walk right through if she has the key now as you can imagine they're also you

know quote unquote flukes where you could say Alice walked in B Bob flipped the coin the coins that come out of B and then Alice comes out of B without the key and this is why this is more probabilistic you want to play multiple rounds of this game if you play multiple rounds of this game probabilistically you can bound the chance that she's really lying to you down to eventually zero the limit goes to it goes to zero and this is a very canonical way of kind of explaining how his your knowledge protocol really works because most of the schemes especially in the early days were designed around interactivity and having this kind of prover verifier challenge as as it's commonly called but so yeah let's Dive Right into things so the first Journal truth was actually invented in 1989 it's by Goldwater mccallion rakoff and back then the model

was basically this you had a prover that had a function f some clean output Y and a private input X you also had a verifier who knew the same function and the same claimed output and the goal was to say the prover says Ah I know some private input such that y equals f of x and the verifier says prove to me that you know X and what they would do is they do this multi-round interaction and communication so the verify would effectively send challenges over to the prover the approver would evaluate those challenges send responses back to the verifier and do this several times and similar to that Alibaba cave example if you did enough rounds of this the probability bounds got you to the point where you could feel confident that well the verify would be convinced that the approver must have the secret if the

approver doesn't have the secret they couldn't answer all of these queries in in a go and so that was the way that this was designed but this as you can imagine uh from from 1989 had a lot of trade-offs first off as you can see it was interactive and if you imagine that this is on the internet and you have you know two random strangers on the internet asking both of these strangers to be online on the internet at the same time to communicate is a pretty big ask and interact activity foundationally is is therefore a challenge the second main thing is that well this design itself was not succinct and what that means is that the actual proof itself to verify it took roughly as long as it would take to compute the function f itself and so if you if you wanted to

say Outsource some work to another party and have them compute it for you well to check that they did the work correctly you'd basically take as long as it would take for them to actually produce the proof and that's not a great guarantee as well and the last thing was to say that it was very it was it had very poor concrete efficiency so the so the prover took a really really really long time to generate the proofs for you and and therefore this was really impractical from a real world context it was it was incredible though from a from a pure academic and theoretical concept to say that you can use math to even make claims like this so in order to remedy some of the issues I just talked about actually in 1994 Sylvia McCallie published a paper that showed the first succinct

non-interactive zkp and the idea there again was to say that there was a prover but now the verifier was actually really really small and so that's the succinct property and you know diagrammatically I showed that that the verifier therefore is very is much smaller and the prover actually made the same claim as before it says hey I know some X such that y equals f of x and the verifier once again said prove to me that you know X and now instead of doing multiple rounds of interaction they use they use basically a random Oracle um you can think about it like shot 256 or Poseidon in this case as now as we now use today but but the premise was was that instead of having to have the verifier come up with some random challenges that then get sent to the approver who then

evaluated it who sent them back to the verify who then sampled some new challenges and and sent them back to the prover to send more responses they could both agree on for example a hash function and say hey like here's the pre-image we're going to start with if we both agree on this we can then hash from here and use the same the same assumptions for what you should be evaluating and then therefore the verifier can just say well I knew what you were starting with and I could iteratively check that you actually use the same the same call functions to to do the actual interaction part normally and this saved on the actual need for both parties to communicate with each other um the end result is that the prover only had to send over one proof to the verifier this ended up being a

non-interactive scheme because of that and this was actually the first ZK snark and so um it's it's been you know like 20 30 years since uh since we've gotten from the original concept of a zero knowledge proof to where we are today uh but there has been a number of of things that have a number of advancements especially in the theory and the engineering that has gotten us to a point where we can now run this stuff in the wild in the real world on very expressive statements but before we start talking about that part I I don't know how many people are familiar with with ZK snarks in its entirety and so I want to just give a quick definitional cons construct for it so zero knowledge proof itself basically ZK snark stands for a zero knowledge succinct non-interactive

argument of knowledge that's a lot of jargon uh what does it mean well zero knowledge means that the proof doesn't reveal the witness the witness is commonly the the private input in this case that's the secret that you don't want to reveal succinct just means that the proofs are small so they're like you know a kilobyte or less and the verification is fast which means it's like you know 10 milliseconds 20 milliseconds something that's that's realistically practical and fast to check in your browser the third is that it's non-interactive which just means that there's no interaction that's needed between the prover and the verifier and lastly it's an argument which just means that soundness holds against a polynomally bounded verifier this is a a more a more technical delineation

because there are statistical bounds and there are computational bounds that one can give for the verifier here and so this is this is one one set of that so hopefully that gives you some some context into what ZK snarks are and now I want to talk a little bit about how you can use ZK snarks to basically build a layer one programming model around it I think the easiest point to start from frankly is the account model because I think everyone here almost everyone here has had some some interaction with ethereum before so before we jump into things I think it's well motivated to say that people really like to build applications uh in in web 3 and there's many use cases for it and the goal is to say can

we build a zkl1 that can support every one of these yes the short is you can but it comes with a lot of limitations the first is that well when when building a decentralized ledger we need to operate by verifying and confirming that each transaction um well Works via re-execution what do I mean by that you have a user who's submitting a transaction and it's composed of the application the input and the signature and the user broadcasts this transaction to the network as so and each node on the network then re-executes the associated computation in that transaction if the computation is correct and the

signature is valid well the application gets updated and as you can already begin to see there's a lot of re-execution that's going on in this model and so let me walk you through some of the limitations of this first it's that ledger executions really hurts scalability so in general every transaction re-running computations on every node on the network will result in a lot of of wasted work in fact if you just take the ethereum structure from eth1 and I realize that post merge we got to redo the numbers here this is 3000 nodes if we just assume that there's like five seconds of computations in each block and this math already adds up to 15 000 seconds or

about four hours of re-execution that's that's a lot of wasted work and you can naturally see just from the from the previous slides on what a ZK snark is is you probably want to try to um well kind of give a proof about it so you don't have to recompute it and everyone doesn't have to recompute it that's like a that's like a big deal because this model here is well wasteful the the second thing is that ledger re-execution hurts privacy and what I mean by that is that like in the existing models of decentralized applications um you'll learn everything you learn who's the caller you learn who who's the receiver you learn what program you're calling and you learn the logic of the program as well as it's it's data and like this is something that I think requires a lot more Nuance if we're

going to take this out into the web the classical example that I give is to say if I want to send you money uh and you give me your bank account number knowing your bank account number reveals nothing to me about how much money how much money you have how much money you make how much money you spend where you spend it uh when you spent it so it doesn't reveal to me any of these things but if you're given your ethereum address now I know all of these things about you and I can track you also for the rest of time with that and so this is a this is fundamentally just a UI ux challenge that web3 introduces that we need to kind of think about if we want to take this technology out into the real world and so we we built something called Elio

Elio stands for autonomous Ledger executions off chain um alien itself is a decentralized ledger and enables users to execute programs off chain and finalize State on chain The Ledger provides several properties the first is that we achieve scalability meaning thousands of transactions per block the second is that we preserve privacy meaning the resulting transaction reveals no information about option computations and lastly we have succinctness which just means that the resulting transactions are small in size and fast to verify concretely for reasonable parameter sizes we get transactions that are approximately one kilobyte in size and they can verify in less than 50

milliseconds and so our programs also provide us with several properties um the first is uh in terms of functionality we enable uh arbitrary user-defined programs and while isolating them in malicious while isolated malicious programs from honest ones and we enable program functions to communicate with one another in a secure manner so to see how we arrived at this design let's start by analyzing this popular framework called the account model so in the account model you basically have a decentralized ledger that's tracking Global state and to perform a state transition the user usually signs an input a transaction sorry that produces a request to say hey please execute this program with the given input Fields And

once the transaction has been verified well it's confirmed into the next block by The Ledger and the account State updates itself automatically it's it's an internal operation and it transitions from the previous state into the new state of the program the intuition here is that users invoke programs with these inputs via transactions and The Ledger updates that internal State based on the outcome of those of the of that transaction naturally one of the biggest benefits of the account model as you guys know is Simplicity it's really easy for developers to coordinate and manage State between multiple parties but there's a few trade-offs of course one is that there's there's kind of a scaling problem there's also a high fee problem and they're Duels of each other in the sense that complex tasks can be time consuming and the large cues of

unconfirmed transactions can build which causes significant spikes in the network fees to occur and the last one naturally is that there's just no privacy in the account model today and what I mean by that well transactions reveal the contents to everyone on the network this means the sender the receiver the program inputs outputs and state are all publicly known so what what do we want to do we want to redesign this Ledger and we want to minimize the re-execution and maximize privacy and so how do we do it well let's just sprinkle some ZK snarks on it of course we want to we want to extend the account model and see where we land here so let's take a first attempt at extending this and the intuition is to say let's start with private smart contracts instead of revealing in the transaction

your value the the data the call data and and the signature why don't we move things over into saying let's commit to the values let's encrypt the data and instead of using a signature let's start using cryptographic proofs as we talked about and for on-chain state with your account instead of publicly showing your balance and publicly showing your code and publicly showing your storage why don't why don't we why don't we commit to the balance why don't we create a predicate about your code and why don't we encrypt your storage then from here we could say what now when a user is creating a transaction they're really revealing a transaction that has very little very little

publicly reasonable data um and what's what's been updated on chain is not the actual data itself but commitments and encrypted data from the previous state into the new state that's the that's the rough intuition on on doing this now if if it were this simple I don't think I would need to be here talking about this design so let's start let's start thinking through some of the some of the properties here in this design why this doesn't work well for one concurrency is a really big problem let's say you have user a who wants to make an update so he calls with transaction One update program a if Trends if party B comes and says I also want to update in the second

transaction this actually doesn't work because the entire state is now encrypted only one party at a time can actually go and update that state because you have to miracleize things in a cryptographic system and your root is a is effectively expiring as you're making that state transition the second issue is that we still don't have full privacy in this account model why because everyone can see that user one updated program program a and the reason for that is if you if we go back just a few slides here the transaction still reveals the address not only the address of the user but the contract address that you're referring to and so if I were in that

bank account model saying I want to send money to you give me your address I might not know anymore how much you're spending or how much you're doing but I clearly can see you're using this account and I can see which applications you're using and I can still cluster and deduce how frequently you're transacting and where you're transacting you can also still figure out who's paying you for your salary and also who's paying you in general to say pay back debts or pay back loans and and this this then therefore says this is not full privacy at least in in the canonical definition so let's analyze the properties more concretely the first is to say we have no more Ledger re-executions why we use a zero knowledge proof and with the zero knowledge proof we're able to achieve scalability and succinctness

the second thing is that we achieve data privacy as we as we said there's no account privacy but we do have data privacy because we're using commitments and encryption to hide program State itself but the as we just said the address can't be encrypted because in the account model you're indexing by address and so as part of that The Ledger fundamentally relies on it to index into Global state fourthly we have a lack of efficient State updates why as we just said we have to consume the entire program in order to make one state transition about it that's not a great model like imagine if if you want to update your C20 and you have to reason every other person's account as well in order to make one cryptographic update and lastly of course there's no

concurrency because when one person makes the full update you invalidate the ability for another person to update the same state at the same time so the proposal that we came up with was to say let's introduce something called the record model what is the record model well in the record model The decentralized Ledger still tracks or Now tracks the records of of each account in global State and to perform a state transition users generate a transaction Computing a zero knowledge proof that attest to the state transitions for the given execution once the transaction has been verified and confirmed into the next block of The Ledger the program updates itself internally and this transitions that previous state into the new state of the

program the intuition here is that the users only consume the records that are necessary to make the state transition that they want for their program in their context and and and this no longer requires you to consume that entire state so because of that you actually get concurrency because I'm only reasoning over the records in the account that belong to me and then I'm going to take those records and produce a state transition out of it the second thing is that this also enforces double spend conditions why because your account state is now properly indexed using records if I'm going to try to spend this record twice it can be easily detected on the network

that this record was previously spent and I can't re-spend this record again and and this model then gives you some some way for consensus to easily check cryptographically that that indeed this state was only used once without actually seeing the contents of the record so when we come back to it now that we have abstracted into a record model we actually get um account privacy why because the decentralized Ledger indexes Global State based on these program IDs these IDs end up becoming the actual clustering Point as opposed to your account address and that that fundamentally changes the assumptions that are being made um in in in in the Privacy model of programming

we also get very efficient State updates because you only need to consume the records in a program that belong to you or the ones that you actually want to use in order to perform the state transition and lastly you can also do simultaneous updates because within a program you now have this record system which says that you only need to consume the records which belong to you in order to perform your updates and and other people can touch their records to perform their updates and and this type of isolation is what enables multiple parties to interface on the same same application at the same time so hopefully that that helps give you some color into how you design the record model in this context and lastly I want to just say like we want to instantiate this so how are we going to

instantiate it well in order to instantiate it we have to use a lot of Technology a lot a lot of disciplines in order to come together and build this thing and Alia is at the intersection of several different disciplines everything from algebra sorry everything from mathematics to complexity Theory to cryptography computer security and programming languages we sampled curves that enable snark-friendly cryptographic Primitives and namely we sampled a 377 bit curve with embedding degree 12 which we call BLS 12 377 this curve is great because it supports fast-proof verifications in our Construction we also sampled a twisted outwards curve and it's useful for efficient Peterson hashes and commitments as well as

signatures and in general Edwards BLS 12 enables efficient circuit operations finally we instantiate our snark our snark here is is Marlin Marlin itself was published at eurocrypt 2020 and modern's great because it requires only a single trusted setup for all programs this is the universal setup that Alex previously was talking about if you'd like to see our work the good news is it is open source um the work here that we have is with respect to Leo Elio and the AVM itself are all on GitHub and and the rationale is to say I can take a very high level piece of language uh called Leo a piece of code in Leo compile it down into

assembly-like language called alien instructions and from there serialize this into into AVM bytecode which then can be deployed on chain so earlier when you saw with the with the programs and Records on there the program itself contains a predicate that's represented with respect to that AVM byte code and all of the code prior to that is is from from off chain from the developer themselves writing out exactly how the the two parties should be interacting to give you just a small taste of what this looks like this is the Syntax for alien instructions you can see here function main I and my inputs start off with registers registers zero and register one in this example what I want to do is multiply these two numbers so I can pass in a public field element and a

private field element I can multiply these two things into register two and then lastly I can output as a private register the field field.private basically the result of that multiplication because this is adhering to the account model what this actually does is say when I want to broadcast on chain the private State I need to encrypt this and this will get encrypted under my account address and so only I using my account can go on chain and see the result of this computation with my with my uh with my view key this is the difference between existing programming models in in kind of evm based systems and the new set of zkl ones that I believe will use a model similar to this lastly I want to say thank you

um Elio is proudly written in Rust we have written a ton of lines of code and we probably need to do some refactoring but but there's been a wonderful community of 40 plus contributors who are building on us and helping to make Elio happen um we are available at this URL github.comhq and lastly test net 3 is live and for those who are interested to play with our Network the developer docs are available at developer.ayla.org and with that I want to thank you for your time and attention and hope you have a wonderful day thanks foreign