Dan Boneh: Blockchain Primitives: Cryptography and Consensus

Transcript

[Music] thank you [Music] so uh welcome everybody I'm really excited that this school is happening this is an amazing opportunity I'm actually really excited to see what kind of apps you guys build and I'm looking forward to this week seven where we get to see everything you've you've designed so what I wanted to do today in the in this in the next couple in the next hour basically is tell you a little bit about the technology behind blockchains I'm I'm really excited about this technology and that technically it's just from a technical point of view it's just

fascinating to work in uh the basic the basic issue is a building decentralized applications is just technically much harder than building centralized applications which makes it very interesting for someone like me so I teach this stuff you know I kind of live this on a daily basis this is going to be a pretty high level talk though this is a rabbit hole that goes pretty deep uh so but I'm happy to go kind of to as much depth as you'd like maybe after after the the presentation I should also say that we've been teaching this uh this class at Stanford now for um what is it five or six years and pretty much the attendance in the class kind of follows the Bitcoin price it's pretty pretty pretty normal yeah you know on a bad day students don't show up on a good day they do show

up all right so let's get started and I want to get started just kind of by explaining my view of what uh what a blockchain is and so I kind of I kind of like to think of it in terms of uh four layers yeah so at the bottom layer we have the consensus layer which just makes sure that every everybody sees the same thing on top of the consensus layers this is layer one on top of the consensus layer we have what I would call layer 1.5 which is the compute layer and here I stole Chris's term the blockchain computer I love this term so thanks for inventing that Chris so it's called a blockchain computer this is kind of the operating system of the blockchain on which you write applications and then Layer Two is basically where the applications run and typically applications will be written in

languages like solidity or move move is the Libra Libra language or motoko and so on and then on top of the applications these are applications that actually run on the blockchain computer and on top of those you have sort of user facing systems that kind of run in the cloud and talk to the blockchain and talk to uh to end users yeah so those are kind of four layers I have to say the consensus layer is getting pretty pretty uh well understood that's kind of there's still a lot of work here but this is kind of not where the most exciting action is most of the exciting action actually is in building applications in fact uh these layer two applications are now starting to be called uh layer two layer 2 blockchains um and so that's kind of where most of the action is and I imagine that's most

of what's where most of you are going to be working in now when I showed this slide at some point somebody asked me uh these uh what you blockchain people you don't know how to count um and the the reason it's a layer one and layer 1.5 is because often these two are kind of combined together but I kind of like to separate them because really there's a consensus issue and there's a Computing issue and literally we could talk about each one of those layers for weeks and so but like we don't have weeks so I'm just gonna say a few words about each layer and then we'll move on to more programmatic advice okay so let's start with consensus uh so first of all the consensus layer again makes sure everybody sees the same data so it provides persistence so once data gets added to the blockchain it can

never be removed and there's an asterisk there uh because there's a caveat the caveat is a 51 attack so under certain assumptions about malicious behavior the data can never be removed consensus means that basically all the participants see all the data the reason there's two stars there is because when we talk about all the participants seeing the same data we mean that that is true perhaps other than the last few blocks that were added so I mean you may have to wait a few blocks for everyone to see everything but otherwise everybody sees the same data liveness means everybody can add data to the blockchain so it doesn't get stuck and finally there's this notion of openness which means that anyone can can be a participant anyone can write to the

blockchain and there's no authentication that's needed to become a member and um and write to the blockchain the reason there's a question mark there is because some blockchains provide openness and some blockchains some blockchains are open blockchains and some are our permissions where not everyone can write so that's the consensus layer I did want to say a little bit about um just a few words about what what uh what it does and so this problem consensus is not a new problem this is an Ancient Ancient problem and by ancient I mean from the 1980s well you know you have uh right so you have systems that people run multiple servers in their data centers and these data centers these systems have to see the same data right Bank of America have has a huge number of machines they all have to make sure they see the same amount of

funds in my account and so that's this problem is called what's called State machine replication traditionally it's actually not called a blockchain it's called State machine replication the difference is that in the traditional world there's a known number of servers and all these servers have been pre-authorized so they've all been given sort of cryptographic material that allows them to authenticate to one another uh the difference with the uh blockchain world or the open consensus world is as we said actually there's an unknown number of participants who can write to the blockchain and they're not authenticated anyone can participate you don't have to do anything in order to participate and the surprising thing is that in fact people have asked can we do consensus in these settings and there's an impossibility proof that says you cannot achieve consensus if you don't

have authentication or you don't have any you don't know how many participants are in the Network and sort of nakamoto's innovation is a way to get around the to get around this impossibility result and I'll talk about that in just a second okay so now that we understand uh what what the Innovation is let's just uh uh talk for just briefly about uh how blocks get added to the blockchain I'm sure many of you have seen this uh before but it's still kind of fun to go through so we have our cute miners over there and we have our participants each participant has a secret key uh which goes back to what Chris was saying this secret key signifies ownership right so you own your tokens you own your data and no one can take it away from you unless you sign it away using your secret key or

someone compels you to give to give away your secret key so how does this work well so uh these participants these users basically sign transactions to use their secret keys to sign transactions they send they send these transactions to the miners now the consensus protocol basically chooses a random leader among these these participants uh the random leader orders the transactions into a block and then the block gets posted onto the blockchain and importantly the leader gets paid by a native currency to the blockchain right so in this case they get a paid to eat and then the other the other Miner is actually verify that the block is valid if it's not valid the block sort of gets discarded there's one thing that I wanted to point out here which is kind of important um which is you realize the minor this

leader that got elected the leader is the one who decided the order of the transactions in a block just think about that for a minute the leader The Miner that built the block decided on the order of transactions that is an extremely powerful position to be in because if a certain piece of bad news comes out about the blockchain you could imagine people are lining up to sell their currencies and who gets to sell first is determined by The Miner this is a this is a a power that can be sold right which is not a good property we'd like to have so ideally we'd like to have a blockchain where uh in fact the order is not determined by The Miner but by by but determined by some Randomness but this is not currently supported so

if you're looking for interesting questions to think about this is really a fascinating one which is how do we make sure that no one not even no single Miner has the power to order transactions as they get put on the blockchain yeah this is kind of an important Point okay so we have this uh this mechanism and then you know a new set of transactions is generated a new leader is elected and the block and a new block is created now you realize and then this new leader by the way also gets paid to eat now you see why the impossibility results came about because um if there's no authentication and no nobody knows how many participants there are what I'm gonna do is let's say I'm the blue Miner over there what I'm going to do is I'm going to pretend like I'm a

thousand different miners even though I'm a single entity I'm going to pretend like I'm a thousand different Miners and then these other two miners will hardly ever get chosen I'm going to be elected every time right there will be a thousand and two miners overall I get elected every time so I always get to collect the two East uh the block rewards for creating these blocks so that attack is called what that's good thank you that's all together now uh so that's called the Civil attack and the whole point then but the impossibility result by the way said if you don't have authentication consensus isn't possible because you're going to be vulnerable to a civil attack and the beauty of nakamoto's innovation is that we can prevent civil attacks uh by uh forcing some sort of commitment to constraint to resources right so we're

going to force the miners to commit to resources and you guys know the story that um in in Bitcoin the resource we're committing to is proof of work right so if I want to pretend to be a thousand miners I have to buy a thousand machines and that's expensive yeah uh of course proof of work has this is basically what's been used in the first generation blockchains I think we're going to be moving away from proof of work it's proven to be uh problematic because of its It's relatively slow it burns a lot of energy so all the criticism that you that we read about in The Press usually criticizes how much energy these things are wasting and the answer is why well no that was just the first attempt at building a blockchain we're moving away from proof of work and actually all the

other ideas are much faster and they don't burn energy or hardly burn any energy yeah so first thing is when someone complains about energy you tell them that well that was the first experiment the future is not is not going to be much more efficient energy wise so we have a lot of blockchains that are proof of stake based systems so again they prevent civil attacks by um forcing people to commit to funds rather than to commit to CPUs proof of space is a beautiful beautiful idea where you say instead of committing to computing power you have to commit to disks yeah and the nice thing about committing to disks or disk space the nice thing about Community this to disk space is that that doesn't take much energy right storing data doesn't take much energy you just have to show that you're storing certain blocks when when

needed and then there are some other beautiful ideas due to Avalanche and others so there's lots of explorations of the of the consensus space um just so you're aware but that's actually again not quite where the action is as I said most of the action is in layer 2 in building applications on top of blockchains okay so let's talk about that so but the blockchain computer so um here I'll go quickly through this uh so so basically you you write applications you post them on the blockchain and then these applications basically respond to events from the outside these events are called transactions right so people send transactions to these programs that are running on the blockchain and the and the and the applications respond yeah so the beauty of running applications on a

blockchain is a um essentially all the code is open source and I have to tell you this is so refreshing working in the space where I talk to a lot of blockchain projects and nobody ever tells me you know we can't tell you what we're doing it's a trade secret which is what I usually hear everybody is very open about what they do all the code is open source all the ideas are out there everybody publishes as fast as they can so it's just so refreshing it's so much fun so much fun to work in the space there are really no secrets because everything is based on trust right I'm not going to trust you you until you unless you tell me how the system actually works so everybody's incentivized to share their ideas and share their code so everything is open source everything is verifiable so we

have this property I like to call that transparency where the world can see exactly how things behave and then we have also public verifiability where I can look on the blockchain and see exactly that all the rules are being followed correctly that the code is actually being executed the way it's supposed to execute and no one is deviating from the rules right so again in the real world you think about that we don't have public verifiability where most of the time we have to trust that Banks do what they're supposed to do or the FED does what it's supposed to do most of the time we have it's based on trust whereas here you could just look and verify for yourself that things are progressing correctly so let's go through quickly how you deploy applications on the blockchain so we'll do that very quickly so you uh write

your code you create an application you write that in solidity you compile it into the evm for example if you're using ethereum then you post your code onto the blockchain with uh what so the this orange thing is the code this blue thing is kind of the initial State for the application and then somebody sends a transaction to the application and basically that causes a state change in the application so maybe some funds moved or maybe uh Chris Dixon got to own cdixon.com right so that that that's the type of transaction that is processed and then you know another event happens in another another state change happens and so on and so forth now in preparation for what's coming I have to tell you that these as I think Chris

said that the ethereum network can trans can process something like seven transactions a second that's way too slow for running all the world's application so really all the focus today is on scalability and basically touching the blockchain as little as possible yeah and I'm going to talk about techniques for doing that in just a minute but essentially when you build your layer two apps part of the goal is to avoid touching the blockchain as much as possible so that things actually scale or I should say to be precise to avoid touching the layer 1 blockchain so the layer two blockchains are much more performant okay good um right so there are different execution environments these blockchain computers provide different interfaces so for example Bitcoin provides Bitcoin script which is a very restricted

language so in particular you don't have loops if you don't have loops you can tell exactly how long every instructor every program is going to take to run so that has benefits but at the same so it's good enough for certain things but at the same time uh there are lots of things you'd like to code up that you simply cannot code in uh in Bitcoin it's interesting like um in our class on payment and lecture on payment channels I can tell you we devote about 45 minutes of the lecture to explaining how many channels work on bitcoin it's fairly complicated and then we devote about two minutes to explain how it works on ethereum because it's trivial yeah once you have a general computing environment building payment channels they're called State channels are much much simpler simpler to build so so yeah so it's restricted but it's amazing in

how much it can still do ethereum is a general purpose Computing environment like we said you program it in solidity um one thing that's that's really important to remember is that uh any data you put on the blockchain is really expensive yeah you have to pay to put money on the blockchain and it's kind of remarkable if you're going to build a blockchain application on ethereum you will not believe how much time you're going to spend removing every single byte from the from from the blockchain from your app yeah so you're going to do all these tricks crazy programming tricks just to reduce the amount of storage on a blockchain today when you want to write the uh data to the blockchain you have to pay when you write and that's it in the future you're actually going to have to pay

continuously for storing data on the blockchain yeah so uh your goal would be to um either expire data as quickly as possible or avoid writing it even in the first place again I guarantee you as you're going to be developing you're going to be spending most of your time in trying to remove data and not writing it to the chain itself so far so good okay excellent all right so yeah so there are lots of execution environments one thing that I wanted to point out is um ethereum uses the evm as a virtual machine uh which is kind of an interesting uh choice for a virtual machine you can see that many of the new modern many of the modern blockchains actually are moving to webassembly so it's a particular bytecode format and

the beauty of webassembly is you get to benefit from all the software development tools that were developed for the web where you can write your application and your favorite language compile it to webassembly and it will just work on the on the blockchain yeah so kind of modern chain modern blockchains are going to have much much more much a much richer development environment to work with just keep that keep that in mind okay good uh right so the application layer is kind of the most exciting part as I said there are lots and lots of applications available already today it's actually really fun to write these applications I have to tell you it's really really fun the one thing you have to be careful with is if you make a mistake if you make a bug in your application you can easily end up locking up 50 million dollars that no

one can get a hold of yeah so mistakes here are really really costly um so the programming language you choose is kind of important there's a a story I like to tell about about solidity so every every time uh you know so so you know solidity is a wonderful first first example of a blockchain programming language but I can tell you every year in our final exam WE Post um an example contract where we asked us we deliberately put five bugs in the program and we asked the students to find the bugs that's our final exam question and I would like to say that I know how to program it solidly but nevertheless every year the students find 10 bugs in the code yeah and so that's just an example of uh yeah it's just an example of what it takes to

write a secure secure code on uh on these blockchains so interestingly more more modern languages like move and motoko they're kind of trying to address that so move a specific design to be easy to verify yeah so there's a lot of work that goes into building automated verification tools so hopefully this problem this problem will be solved uh in the in the future okay good so I think uh maybe I just wanted to mention the last thing is um effectively the layer 4 application at the user facing Services what they do is again we have our consensus layer here our blockchain computer and then we have our apps running this is running on the blockchain but it's important to remember that really what the users talk

the users don't talk to the blockchain what the users talk to are application servers that run in the cloud yeah and so they just you know so the web server is actually run here in the cloud and they just get their data from the blockchain so the blockchain is in some sense the ground truth but really everything is replicated into databases that live in the cloud and end users just see just see that yeah so again if you go to handshake and you try to um uh to reserve to buy a domain name it first gets recorded here and then gets pushed onto the blockchain okay good um so you you probably all know there's a thriving ecosystem of applications right running on the blockchain this picture every time I put up this picture I'm just kind of amazed at how active

the space is so and this is by the way only the decentralized finance world it's not even their applications Beyond D5 this is just D5 um so I think Chris already pointed like one of my favorite uh D5 applications is maker dial it's just an amazing idea like how to build a stable currency using collateral that lives on the blockchain it's just like when you read it you just become happy because it's such a beautiful idea that it's it's a lot of fun to just kind of study and analyze how it works um so yeah I encourage you to read about maker Dao it's just a really really beautiful idea um and it's so far seems to be seems to be working seems to be working quite well so that's maker Dao effectively what they did is they took the U.S fed policy the U.S federal reserve and just

implemented in an algorithm as as a as a short description um okay and then uh you can talk about com uh lending platforms like compound those are very interesting too and these applications literally you can log you can go to the blockchain and just read the code like you know I I stopped actually reading white papers to describe how the code works I just literally download the code read it and see exactly how a compound works it's not that hard it's not that much code and you can just understand it best by just looking at the code so again I encourage you try not to read the white papers or maybe read them just as background but then just go to etherscan and get download the code and just read it it's very clear uh usually it's very nicely commented and you can see exactly

how things operate very instructive okay so uh yeah so we're going to talk about applications actually next week we're going to talk about lots of applications in the coming weeks even and so I'm not going to say more about that here uh what I wanted to do now is uh do a digression how are you uh how are we doing that time okay fantastic all right keep going uh and I wanted to switch switch gears and talk about cryptographic Primitives so I'm a cryptographer so for me this is you know I have to say these blockchains are like a godsend because crypto is like so much fun now right everything that we do gets implemented and deployed and there's some things that we've deployed that are now protecting billions of dollars which is exciting and frightening at the same time uh so

what I wanted to do is tell you a little bit about cryptographic Primitives that are useful on the blockchain so I hope these are things that um you know you will put to use in your own projects um and so again this is a pretty high level description um I'm really happy to go to as much depth as you'd like on these things but which I'm going to try to get through this in like 10 minutes so these are Big topics yeah each one of these circles literally is a huge topic but we're going to do it quickly and if you'd like to talk more I'm happy to stick around and talk more about that afterwards yeah so I wanted to tell you a little bit about digital signatures and particularly aggregating digital signatures then we'll talk about Merkel commitments and finally uh we'll use

those two things to build what are called succinct zero knowledge proof systems uh they're also known as snarks it's a great name uh okay so let's start let's start with digital signatures so I imagine actually many of you already familiar with digital signatures so let me go through this relatively quickly so in the physical world you know what what a signature is you just sign your check but you think about that for a minute and you realize wait a minute this can't possibly work in the digital world because in the digital world I could just copy the bits I can just copy the bits into another check and that would not be cool yeah so clearly what we do in the physical world simply cannot work in a digital world so we have to build signatures slightly differently and so this actually was a people were stuck in the when when these

ideas were developed back in the 80s it wasn't clear how to sign uh in the digital world because of this problem and so the idea it's actually due to Michael Rabin uh is to basically make the signature itself be a function of the data being signed yeah so it's not like the physical world signature where here we're in a digital world you actually look at what you're assigning that becomes an input to the signing algorithm along with the secret signing key and and then these two things together the signing key and the data being signed they're the things that produce the signature okay so now the signature depends on the data then given the signature you can actually feed it into a verification

algorithm the verification algorithm takes what's called a public key okay so that's a matching pair to the private key so the signature the data and the public key go into the verification algorithm and the verification algorithm says yes valid or invalid okay so that's how digital signature Works digital signatures work the thing that's important to understand is if you don't have the signing key or if somebody doesn't have your assigning key they cannot sign in your behalf period yeah it doesn't matter how many signatures they see if they don't have your signing key they simply cannot generate signatures on your behalf so that's what a digital signature is um signatures are used everywhere on the blockchain yeah so they used to authorize transactions they're used in

governance votes I guess there was a Maker Now governance votes right so the way that worked is all the gov folks participating in the governance use their signing key to sign uh to sign the proposal that was being voted on and it's also either it's also used in consensus protocol and particularly in proof of stake consensus protocols uh all the verifiers basically sign and if enough signed then the block becomes real so yeah so signatures are kind of used everywhere you can see that when these transactions get their transactions are signed they get posted on the blockchain and then all the verifiers have to verify all the signatures if you think about it for a minute you realize that's a little crazy right if once minor verifies a signature we know all the signal we know that the miner says the signatures are valid why

is it is it all the other miners now have to repeat the work and verify the signatures for themselves but this is how this this is how it works today okay keep that in mind because we're going to come back to that in a minute okay so that says digital signature um I wanted to also mention this uh space saving idea so there's something called Signature aggregation where you can take for certain signatures you can take a whole bunch of messages signed by different people and effectively compress all the signatures into a single signature this is called an aggregate signature that's a purely compression mechanism you take a whole bunch of signatures compress them into one and now when you want to verify you need to know all their public Keys you need to know all the transaction data and you only need this one aggregate

signature and that allows you to verify that all the messages were properly signed okay so the point of this is that you don't need to store all the signatures on the blockchain you can just compress all them and just store the aggregate okay so again it's a very useful compression mechanism so I just wanted to mention there's a blockchain called Chia that you can see when you post transactions on Shia what the miner does is he takes everybody's individuals signatures compresses them into the Aggregate and only stores the data in a single aggregate okay so this is a really nice compression mechanism to reduce the amount of data stored on the blockchain and remember our goal is to reduce the amount of data as much as possible

okay good so keep that in mind there's this nice compression compression trick that everybody can take advantage of all right the next thing I want to talk about is Miracle commitments actually I am really curious how many of you know how Merkel commitments work ah okay not too many so oh okay so I'll explain it at a high level so let me explain what a cryptographic commitment is yeah it's uh yeah so what's a cryptographic commitment so a cryptographic commitment basically functions like an envelope all right so imagine imagine we wanted to run a sealed bid auction how does a seal bid auction work in the real world right everybody takes their bids sticks them into an envelope seals the envelope sends the envelope to the auctioneer the auctioneer collects all the envelopes

right once they're all at the auctioneer's hands he opens up all the envelopes and then decides who won the election who won the who won the auction yes so well a cryptographic commitment does exactly that right so you can allow you can put data inside of an envelope send it to the auctioneer and then later on the auctioneer can open the commitment and recover the data right that's basically what a cryptographic commitment allows you to do very very important primitive in the blockchain world so let's define it more precisely basically there's an algorithm that will take some data and will produce a commitment string that's the thing that's going to be sent to the auctioneer and then there's some opening string that's going to be kept secret then there's a verification algorithm that's going to be run by the auction

house that allows you to basically say oh the data that was in the commitment is this data over here and the opening string is the proof that the data is correct okay so I can commit and then later on I can open but I can only open the commitment in one particular way so the properties of a commitment schema is exactly that that there's a binding property that says I cannot I cannot open the commitment in two different ways once I've committed to something I'm bound to that data and then the hiding property says that if I give you the commitment string you have no idea what data I committed to yeah it's in the envelope and you cannot see it the reason this is such an important primitive is what I can do is I can commit to data on the blockchain I can

literally put data on the blockchain I'm about I am bound to that data I can no longer change what it is because of the binding property but because the commitment is hiding nobody knows what data I posted onto the blockchain yeah so that's that's why this is such a useful mechanism in this context okay so there's a very famous commitment scheme uh well actually there's a Merkle tree commitment which as I described it it's not hiding but it could easily be made hiding where what you can do is you can take a whole bunch of values and produce a very short commitment to those values very when I say very short I mean like 32 bytes just 32 bytes there could be a million elements in the leaves here yeah so this could be gigabytes of data and

yet you're compressing it to 32 bytes in a way that you're committed to all of these values and more importantly later on if I want to convince you that element number four is X4 I can produce a very very short proof it's like a kilobyte proof that will convince you that X4 is really what what I committed to yeah so I have a huge set of data I commit to this huge set of data but now I can prove to you I can open individual cells and prove to you very efficiently that the cells were are correctly that what I showed you is the correct value in the cell okay so this is called a Merkle tree very important again very important idea this is basically deployed in all the blockchains out there yeah so uh I wanted you to see how

it works the one way to use it for example is to convince someone quickly that payment was made so imagine we have a thousand transactions in one particular block okay so here's one block we have a thousand transactions we actually don't write all the transactions of the blockchain instead we're just going to write a miracle commitment to the blockchain so again we minimize the amount of data on the blockchain yeah so we just write this short hash to the blockchain but now if Alice wants to prove to Bob that she really paid him to eth it's really easy for her to do because she can produce this very short proof that says yes I this transaction is part of what was committed to the block to to to on the blockchain yeah so again Alice can produce a very short proof to Bob

Bob can check the proof Rob has all the block headers he can check the proof and be convinced that Alice really paid him but you see again we're moving data off of the chain which is kind of what the game all this game is about reduce the amount of data on the Chain itself okay good so that's one application uh yeah easily uh do giving proofs of payment the other application I wanted to mention is that you can actually keep a whole database off of the chain using this trick so imagine we have a bank and the bank actually maintains everybody's balances right so Alice has 10 coins uh you know Bob has five coins and so so on and so forth we can commit to uh this entire database using a tiny commitment string 32 bytes that's that's the only

thing that's going to live on the blockchain but now if Alice wants to prove that her balance is 10 it's actually quite easy for her to give this proof that uh just by looking at this hash value anyone can be convinced that she really has 10 uh 10 tokens in her account yeah so again it's a way to keep an entire database off the chain the first thing that would come to mind when you try to design a system like this is to write the entire database onto the blockchain what I'm telling you is you should never ever do that yeah that's kind of not a good design it's better to keep data off the blockchain there are some techniques lots of technical issues come up in in um in making this work there's something called the data availability problem that you have to get around so there's lots of technical

issues in making this work but this is a wonderful way to keep data off of a blockchain okay now if a transaction actually happens uh say Alice paid Bob two tokens you can see Alice's balance went down and Bob's balance uh went up here I can show you again yeah you can see Alice's balance went up went down Bob's went up uh and then all we do now we have to update the database so we just commit again on the next block we commit to the updated version of the database yeah so every time there's a change we just commit to a new version um and still everybody can prove that their balances are what they're supposed to do they're supposed to be and the only thing that the sort of the program on the blockchain needs to check is it that is it this transition is a valid

transition all right so that's how Market commitments are used again we're building towards towards a tool that's uh that I'm going to mention in a minute so this is an important component of that um great so the last topic the last primitive I want to talk about is uh what's called a zero knowledge proof system so these are these are kind of things that zero knowledge proof systems are the sort of things that uh you wouldn't believe are possible yeah if I just told you what they are you would go no no surely you can't do that so maybe the easiest way for me to explain what a zero knowledge proof system is I'll explain it like I have to give a talk to uh kindergarteners one time about uh crypto so and I decided decided yeah well I decided to explain zero knowledge

proof systems to them so so the question is how how to do that and the example I came up with was um was uh where's Waldo do you guys know that where's Waldo puzzle right I'll give you a picture with a thousand faces and I want to and uh the challenge is find Waldo so I want to prove to you in zero knowledge that I know where Waldo is in this in this image yeah so I walk into a room you show me the where's while the puzzle and I I can see Waldo and I want to prove to you in zero knowledge that I know where where Waldo is yeah so that's a puzzle for you you guys can think about how you would do that but maybe I'll just tell you yeah so here's one here's one one simple protocol for doing this it requires scissors yeah so what

what I do is you give me the the picture with a thousand faces and I find Waldo and I want to prove in zero knowledge that I know where Waldo is can somebody see how would you how would you use scissors to do it oh oh but then they could separate they can separate the two pages and then and then they'll know where Waldo is that wouldn't be zero knowledge but you're on the right track what you would do is you would take the scissors and simply cut Waldo out of the picture out of the challenge picture with a thousand faces and then you actually would turn around right and then cut it kind of behind your back and then you would rip the remaining picture so the that nothing is left of the shredded nothing nothing is

left of the original picture and then you can give the Challenger you can give them the picture of Waldo and um Unfortunately they have to they have to search your pockets before you do this to make sure you didn't walk in with a picture of Waldo but if um if if you're okay with that then that's kind of a zero knowledge proof that uh that you know where Waldo is and he learns nothing he or she they're nothing at all learn nothing at all those okay so the kindergartens by the way asked me well why do you want to do that in the first place so so that didn't work that didn't work very well but anyhow it gives you an example of what a zero knowledge what what is it yeah that didn't work at all by the way they were not they were they

were not impressed but but the point is I can prove that the amazing theorem says that I can prove anything that can be proved can also be proved in zero knowledge yeah so if a certain fact has a short proof I can convince you of that fact without telling you anything about what the proof is yeah let me give you an example of that so let's suppose so here we have approver and a verify right the prover wants to convince the verifier of a certain fact so let's imagine this the what the prover is trying to prove is that he has a signature on a particular statement so maybe there's a transaction in question this is called the statement that I'm trying to prove I have a signature on this transaction and then there's a secret witness which is the actual signature yep what I'd like to do is

prove to the verifier that I know a signature on this transaction in zero knowledge which means that I learn I leak nothing about the actual signature okay so the statement is yes the verify says approver has a signature on a transaction the approver will send a proof to the verifier the verifier will either accept or reject the proof If the verifier accepts the proof he is actually convinced that the prover has a signature but he learns nothing at all about what the signature is yeah it's an amazing fact that this can be done but it actually can be done this is something that was proved back in the 1980s but in a very theoretical fashion in that normally this would be quite inefficient I have to tell you because of the blockchain world in the last five to six

years there's been just mind-boggling progress in making this work and now these things are actually actually implemented deployed there are there's a whole software tool chain that allows you to build uh to build these your knowledge proof systems um there's a system called circom that where this is what we use in our courses where you can actually program these statements and then build easier and Order proof system systems automatically so it's really become a very applied and very practical field so it's amazing it's amazing to see this happen uh okay so what's a statement as I said a statement is just basically a program that's applied to to two inputs the statement and the witness and you can prove that given a statement you have a witness that makes the program output

one yeah that's kind of what the zero knowledge proof system does great so what do we use oh yeah actually first of all so what are the properties of these proof systems especially understand what they provide uh so first of all if the statement is true the proof exists yeah there's a way to convince the verifier that's completeness uh the proof has to be short okay so it's very important to prove me short because these proofs are going to go on the blockchain so we want them to be short because we always try to save bytes on a blockchain okay so you have to be short they have to be fast to verify why do they have to be faster verify because all the miners have to verify them so they have to be really really cheap to verify and then they also have to be relatively easy for

the prover to generate okay so if you have all these properties this is what's called a snark yeah so snark stands for succinct non-interactive arguments of knowledge yeah forget that just remember it's called a snark it's a really really cool name uh now it has to have some security properties in particular you shouldn't be able to prove a statement that's false yeah that's called soundness and then uh optionally you could also have a zero knowledge property which means that you learned nothing about the witness if you have the zero knowledge property this is called the ZK snark okay so there are two types there's a snark and there's a ZK snark and they have different applications so let me show you up in one application for a snark and let me show you one application for a ZK snark and then I'll stop

does that work okay let's do it all right so um the application for uh for a snark is actually kind of a big deal now it's called roll up so Roll Up is now taking this is an idea that's taken over the world yeah so these are called uh levels it's now even called a level two blockchain and so let me explain the idea behind roll up so I already complained to before that the way blockchains work today is somebody posts a transaction one Miner verifies it posted on a blockchain but then all the other miners have to verify it as well it's a lot of wasted work for all the other miners you see everybody's verifying the transaction so roll up says let's get rid of that let's make things way more efficient and so we introduce a central server it's called a

roll up server but of course anyone can run a roll-up server so it's Central centralized but it could be arbitrarily replicated um and then instead of sending their transactions to the to the miners all the users are going to send the transactions to the rollup server what the rollup server is going to do is he's going to verify that these transactions are valid so he's going to verify all the signatures verify all the account balances everything is going to be all the checks are going to be done over in the rollout server and then what the rollup server is going to do is it's going to generate a snark proof that all the transactions are valid okay so this proof Pi yeah Pi stands for proof is a is fast to generate it's convincing and

it's super fast to verify yeah so you can roll up a thousand transactions into a single proof and verifying that single proof takes like five milliseconds yeah so all the miners have to do now is just verify proofs rather than verified transactions so this guy does all the work and everybody else benefits from it yeah that's the idea of of roll up this is an amazing way to scale a blockchain because here you can actually have like a thousand transactions possibly even 10 000 transactions rolled up into a single message onto the blockchain and by the way it's called roll up because uh you also send a summary of the transactions onto the blockchain so that gets written the summary gets written to the blockchain so if somebody

wants to they can start at the beginning of time and kind of go through all the roll-up transactions and rebuild for themselves the current state of the world yeah this this is kind of important this is what this is a primary characteristic of roll up that the actual transaction data gets written to the blockchain just nobody needs to verify this data because the proof proves that it's legitimate okay so that's that's roll up uh beautiful idea for uh for uh for a snark you realize we didn't need the zero knowledge property here all we were doing is that all we were using is the property that these proofs are efficient to verify there's no need for zero knowledge people still do zero note by the way it's called a ZK roll up people still do zero knowledge roll ups uh just to make sure to provide some privacy so

that the miners don't even know what their transactions are so we can even do provide some level of privacy from the miners but not privacy from the from the roll up server turns out with a bit more work you could even provide privacy from the roll up server but that's that's for another day so that's one application the other application I wanted to mention is one that right now is a bit of a dream but this is what we're working towards okay this is a still science fiction um but we'll get there yeah we'll get there for sure and this is again really important to remember especially in the context of the all these uh Central Bank digital currencies yeah it's really really important to remember that you can have private data on a public blockchain yeah let me explain why this is so important so today essentially all

the data that's posted to the blockchain is available in the clear all these transactions are available in the clear this basically means that it you know it's not usable for many B2B applications for example you know if Apple wants to pay Foxconn uh in in a digital currency everybody could look on the blockchain and just see exactly how much apple is paying Foxconn which is not something Apple being Apple would want public yeah uh what's important to remember is that you can actually this is not necessary you can have private data on a public blockchain so let me explain uh what I mean by that so rather than writing the application code in the clear and the transaction the application state in the clear what we can do is we can write

commitments to the application code and commitments to the states onto the blockchain so we're committed to what the data is to what the application code is it's just nobody knows what the application code is it's inside of a hiding commitment okay and then when a transaction happens when we need to move to a new state so here you can see the transaction is hidden we only post commitments to the transaction onto the blockchain and we post a commitment to the updated States what we do is we also update a zero knowledge proof that says that uh this state transition is valid State transition is done according to the committed code okay so just again this is a little bit mind-boggling that this is at all possible it's kind of an amazing idea that you can have secret

code secret State and you can have um uh you know updated secret State and even though nothing is public everything is hidden you can provide a zero knowledge proof that the code was applied correctly to the state and the transition is valid yeah so you have this property called public verifiability where anyone in the world can verify that all the rules are being followed correctly the code is running correctly even though nobody has any idea what the code does and nobody has any idea what the data is and you yet you can verify that everything was done correctly it's kind of magical yeah that it can be done but it's it can be done I'm telling you it can be done and uh we I'm happy to actually explain how it's done but we would take we would

have to be here for another three weeks it's actually really pretty it's really really pretty I would actually be excited to tell you it's it's really cool uh yeah I don't know it's what can I say it's just tricks with polynomials yeah if you like polynomials you know go look at how this stuff works because it's really really pretty how it works just tricks with polynomials okay so then basically all these transactions sort of happen the state evolves and every time we have a state Evolution we just provide a zero knowledge proof everything is verifiable but the data is completely hidden yeah so if anybody tells you we're going to be running a private blockchain because we're worried about privacy you tell them that's the wrong solution you should be putting your data on a public blockchain and just use zero knowledge proofs yeah

that's much better it's better for interoperability it's better for public verifiability and it's just better all around all right so that's the Whirlwind tour of the crypto Primitives I wanted to tell you about so one thing that I want you to remember kind of drives me nuts sometimes I talk to folks who tell me we have some data so we're just going to throw it on a blockchain yeah that's not what A blockchain is for yes it's not a database yeah just remember a blockchain is not a database basically the question is always to ask whenever you come up with an application you think you have a really cool application for a blockchain the first question you need to ask is why can't I just use a centralized system centralized systems are a million times easier to build than a decentralized ones they're a million times faster if

you can centralize centralize yeah it's just when you cannot centralize that's when you decentralize so basically if there's no single party distrusted by by everyone that's where you have to to decentralize but of course you get complexity and and speed issues as a result yeah so that's one point to remember it's not that everyone who has data needs to put that data on a blockchain that's not what quite what it's for the second thought I want I want to leave you with is you guys remember in the early days of social networking there were like a bazillion social networks out there yeah and what happened at the end yeah what happened at the end was that we were left with a relatively small number right now we're kind of at the age where people are experimenting with lots and

lots and lots of blockchain architectures yeah so right now we're kind of at the age where there are lots and lots and lots of architectures out there and well you know maybe there will still be many blockchains out there in in many years but it's very likely that we'll converge onto a small number of architectures yeah and so which ones those are I wish I could tell you it's too early to tell uh but yeah this is why it's so much fun and you know I encourage you to kind of uh play with these with these ideas and who knows maybe your design will be the one that gets Chosen and that's what the world will converge to okay fantastic so I think I'll stop here I'm really looking forward to seeing everything that you build and uh yeah thank you very much [Applause]

for the Roll-Ups the server that's hosting the actual the code and the algorithms for it is that a centralized server so the server that's actually building the proofs that's a centralized server but it can be replicated so in other words the the fear is that you might have censorship right I mean the server might the server can't cheat you because it's providing a proof that everything that it does is valid and correct what the server might do is it might refuse a transaction from you yeah censorship so the way the way around that is well there could be multiple servers multiple entities that provide roll-up services and you could choose anyone you want they don't need to talk to one another they come to consensus through the layer

one blockchain right so they push these hashes to the layer one and then uh the layer one basically enforces consensus if anyone tries to uh let's say if two of them try to post transactions that are conflicting the layer one basically will resolve will choose one of them and we'll go with that and the other one will get will get rejected because the zero no the zero the zero knowledge proof will no longer verify yeah yeah yeah it's kind of a pretty cool design yeah yeah yep that use snarks could you recommend libraries that abstract away the underlying complex yeah there are many high level Primitives look so there's a like I said we we use cerecon because it's the easiest one to come up to speed

with so we don't spend to spend a lot of time learning that but there's Socrates there's uh snarky there's a uh Json Arc I mean there's now there's zinc which is uh which is a kind of a cool zinc is one that you can write in Rust you literally write your program in Rust and zinc will compile that into a snark yeah uh it just yeah uh circom is the easiest one to learn but there are lots and lots of options to choose from yeah thank you yeah when you got to the slide about private data on a public chain you said this is still a dream ah why why is that still a dream not a real like what needs to be built yeah good good that's a really good question so it's it's actually we're almost there so so um if all you

if all you want to do are just simple simple uh fund asset transfer transactions that we can totally do today yeah in fact that exists today already um if you if you want to do more complicated transactions like you want to run the entire an entire evm program inside of a snark you know that's that's going to take a while so generating the proof the proofs will just take take a while uh the nice thing the good thing though is these proof systems are getting better and better and better in the sense that uh the bottleneck the bottleneck right now is the time to generate the zero knowledge proof that overhead keeps shrinking yeah we have better and better systems and um yeah so basically the the time to generate the proof keeps shrinking because the algorithms get better and eventually the hope is that

we'll get to a point where we can run arbitrarily complex program programs inside of a snark we're not yet we're not there yet today um but then at the same time you know most transactions are just asset transfers and those we can handle already using the existing existing technology so we'll get there I'm I'm confident we'll get there so that's that's the goal this is by the way why it's so much fun right I mean this is kind of uh you know I'm a cryptographer for me you you're kind of dangling uh you know it's like a red clock dangling in front of my face saying you know build us these snarks and it's like I can't believe you guys are asking me to do this it's like my dream thing that I like to think about so this is why it's so much fun

oh yeah yeah you emphasize in your uh talk importance of not putting data on the blockchain uh how uh you uh advise to go around data availability problems uh like currently for instance that you put data not in the state but in a first as call data called it yeah uh are there any but more sophisticated ways of doing this and yeah so the current roll-up solutions they just put put all the data in call data so so at least it's somewhat compressed um but there are other other proposals out there so for example um one one idea is uh you have a

committee that replicates the data and then you declare that the data is available if all the committee members sign yeah so you're kind of relying on 100 party 100 parties basically to provide data availability for you yep so instead of pushing everything to the blockchain you just have to push these hundred signatures to the blockchain and then we say the data availability has been done and if you need to date the data presumably you go to any one of those hundreds or a subset of those hundreds and you can recover the data so that's like that's a pretty promising fairly promising technique um but today basically call data pushing call data to the to the blockchain is basically what what you have to do with rollup yeah so yeah so you're right this is this is expensive and over time I guess is we're going to move to these

committees yeah it's a good good question yeah um so this actually might be related to that question but so recently on ethereum um someone had written an obituary for the Chinese scientists who had um I guess raised the alarms for Coronavirus and in that case you know data is being written onto the chain and maybe the goal there was to avoid censorship by the Chinese government so I guess I mean given that um and your comment about keeping data off of the chain I well the question would be maybe like would censorship be a reason to actually to use a blockchain or is there a better

solution that's a really good question so if you if you had to could you use the chain as a way to just prevent it from being removed yeah absolutely actually in fact there are a number of projects that do exactly that they use they use a blockchain for uh for replication in fact that's kind of what filecoin is is doing so the data can never be removed so those I would say those are changes that are specifically designed for data storage so they're the cost of storing data on the chain is not as expensive uh and that that is a wonderful application for that yeah so you you put the data there like on filecoin and or or any one of these other systems and um because of replication it's very difficult to get to make the data disappear so yeah

that's a perfect application but those are specific blockchains that are designed for that purpose so it's a really good point thanks I've met a lot of VCS that talk about the deals that they've passed on that became billion dollar companies and bitcoiners that talk about the keys that they forgot on that old laptop and destroyed um I find I worry a lot about key management for my users is there a way to do it without doing custody oh boy you that's a difficult one uh right so yeah so there are there are well what

can I say so there are some proposals well there look there are many proposals to try to address exactly that so there are some proposal proposals to try to address this using um using Hardware enclaves so you do custody to a remote party but the custody lives in a hardware Enclave so they can't abuse it unless you authorize it um uh right so there are there are ideas floating around but yeah but what can I say you you're right I mean keeping Keys yourself even though it gives you the comfort that no one can take can take the assets away there's also a risk that you might lose your keys um there obviously as you know there are combinations of the two right where you keep where you do a two out of three secret sharing where you know you keep

one share and there are two servers that keep the other other shares so even if you lose your data maybe you can use those two servers to recover your to recover the assets nevertheless um so there are solutions so I would call that partial custody right so there are lots of people exploring different ways to do partial custody um yeah and that that's quite popular of course full custody is kind of popular very popular as well um then you know I have to say the nice thing about this world the world of of these assets digital assets is that the user has a choice right today with the financial world today you have no choice right um you know if you think about your car ownership slip your your uh housing house ownership all that kind of lives

in a custody-based databases you have no choice that's basically how the world runs the nice thing about this is you can choose right if you are you know if you if you are worried about custody and you want to keep the data for yourself you can just keep the keys yourself there's risks to that but if that's what you want you can do that uh if you want to have a custody solution you can do that too if you want partial custody you can do that too so in some sense it's kind of nice that we can service more of the you know more more of people's uh you know needs and you know give them whichever level of comfort Comfort they want so I think that's actually a pretty powerful capability that's not available today okay so thanks Dan yeah thank you very

much [Applause] [Music]