zkSummit - Zk0x02 - An intro to Zcash and zkSNARKs - Ariel Gabizon (Zcash)

Transcript

[Music] okay so this is gonna be a introduction but you know kind of maybe adapted to the crowd here so I'm gonna try to give some intuitions about how the the Z cash protocol works and how snarks work okay so so the Z cash protocol let's let's go for a second to Bitcoin and think of it through the the following analogy so right the main object there is the

unspent transaction output set and you can think of that as some bowl that everybody can see what's in the bowl and and this bulk ball contains everybody's unspent coins and what is a coin right a coin is like an address and and the value and and let's assume for simplicity that all all coins are $1 all right so it's some given point in time these are the the current unspent coins Alice has to Bob has to and so how does payment happen in Bitcoin when you're thinking about it like this Alice wants

to pay Bob so she she creates like a new Bob coin she puts it inside the bowl and at the same time she takes out an Alice coin and the the idea is that since everybody's looking at the bull everybody can see that yeah she really took out one of her coins and she put in what what she took out so so everything is fine but of course you have there's no privacy in such a system at all because everybody is looking at this bull so in in Z cache you can think of it

that we replace this bowl by an opaque box so you can't see into the box this is just for the presentation and and think of this box is having you know a small opening on the top so so this is a box that you can you can drop things into but but you can't take anything out once it's in and and you can't look inside so and also think that we've added to each coins some some random serial number we've chosen some random number and added it to the to the coin

but think of all these coins still is one dollar coins so so the big difference so far from Bitcoin one big difference is that you know once something's inside the box you can't take it out and of course you can't look into the box all right so we need some way to distinguish between spent coins and unspent coins right so we're gonna add next to this box a list this list everybody can see the the list and what what does this list contain it contains

the serial numbers of all coins that have been spent up to this point so say at a certain point in time out of these five coins only this coin of Alice was spent so so this list will contain just this number for four to one and right this this serial number it's just a random number it doesn't give you the the ID of the of the coin holder okay now the right the question is so

how does Alice pay Bob in such a system so he like in Bitcoin she's just gonna create a a Bob coin and she wants to now drop it in in the box but before she drops it into the box we we ask Alice to write a new number on the list a number that's different from what's on the list so far and what is this number Alice is writing on the list it's a serial number of some coin of hers that's still unspent so for example if alice is going to use this coin to make this payment

now she's going to add this serial number to the list all right so right so basically the idea is instead of preventing double spending by taking spent coins out of the of the bowl we prevent up double spending by requiring requiring unique numbers on this list but of course at this point this could all be nonsense because we don't see into this box so how do I know

that this number that Alice is writing on the list is not some completely random made-up number that doesn't have anything to do with with anything and you know as you can guess the answer in in two words is ZK snarks so Alice will will somehow use ZK Snorks to prove that this number she's writing now on the list is really a serial number appearing on some coin in the box a coin that says

Alice so that's the Z cash protocol in three four minutes and now I want to give you some intuitions about ZK Snorks so I like the most this is a kind of advanced definition of snarks I heard Zuko Wilcox give that a snark is a bunch of words scientists put together so their

initials will spell snark it's a very advanced crowd so I can use that definition it corresponds very closely to something Sylvio McCauley called computationally sound proofs somewhere in the beginning of the 90s but snark is is more tweetable and retreat tweetable than computationally sound proofs so i want to give you some intuition about what i see is the two main ingredients in making a snark and the first ingredient is that we're going to move our statement to the world of polynomials why are we going to do that because basically if you tell a lie in

polynomials you need to lie most of the time and just as a historical anecdote this this kind of idea it appeared first in a really great break for work that what this work allowed us to do is say there's a Sudoku puzzle that there's no solution to and I want to efficiently prove to you there's no solution to this Sudoku puzzle right if forget zero knowledge for a second if I wanted to prove to you there is a solution I would show you the solution say I want to prove to you there's no solution I want to do it quickly without you having to go through all the

possibilities so this classical work of Lulu and for no Carla phanie son allowed to efficiently prove what's called qohen P statements of the form for example there is no solution to this Sudoku puzzle so if you tell align polynomials you need to lie most of the time let's give a concrete example of what I mean by this so say for example the the lie you wanted to tell was you know this program here that starts I starts from zero in ten times we increased I by one I want to tell you the lie that this program outputs eleven

so now I'm telling you I want to tell you the story of how this program ends up outputting 11 so I tell you the story of its execution of how the state changed how the value of AI changed and you know I tell you the story well you know I I was zero and then we had this plus plus command so the state of I became one and then again we had another plus plus command the value of I became two I continued you know you're getting bored I'm just I'm you see I'm not lying it's just some formality and then when I see your ear a little you know a little bored and not listening and I say and then suddenly at this there was a point where I was six and then you know there

was a plus plus command I became eight you know I slipped that through you and then you you know you wake up little and and then I continued not lying you know and then you know I was eight we there was a plus plus command it became nine so so so the point is when we're talking about program executions if I I slip in slipping in one lie is enough to make to successfully make a completely false statement I only need to lie in one place to get a completely wrong conclusion okay but but now the idea and

this is kind of the the basic important idea in snarks the the first of them is suppose I tell you now all right tell me the story of this program executions but tell it to me as a polynomial what does that mean tell it tell it to me as a polynomial I'm saying well so what is this story it's I can think of it as as a seer as ten numbers right the ten changes in the in the state of AI and the value of I so you know I have ten values you know what's called Lagrange interpolation there's some degree at most nine polynomial that gets these 10 values that and at these

10 time points will output these values so I tell you you know find this polynomial and you know tell me its values but you know do me a favor you know tell me its its values not on these all just these ten points that correspond you know to the program execution if you've already found this polynomial you know just write to me what its values are also on you know on other points and you could say why the value of this polynomial and other points what does that have to do with the program well just just do me a favor and write write them for me and you say okay so so

say you weren't lying so what is right that what is the true story I always changes by one at any time point so I need a function that x equals 1 gives me 1 x equals 2 gives 2x equals 3 equals 3 what's the degree at most 9 polynomial that gets these values it's not too hard it's just the polynomial the this the constant one that always returns one so and how does this polynomial behave on the numbers 11 12 what is f of X f of xi f of 12 of 13 it's just 1 so if I'm not lying this this is what what I will give you but now the important point is that

say I am line and just at this one point you know that I wanted to falsely claim that at this one point point I grew by two instead of one so the point is that now my lie will manifest a lot very clearly so so so now I need to find a degree nine polynomial that gets these weird values 1 1 1 1 1 and 70 2 and then 3 more ones so you do what's called Lagrange interpolation you find such a polynomial this is just an approximation it's going to look something like this you point zero Zhu something two times X to

the ninth and so again on points one to ten it's very close to the to the true thing but the point is that now outside this range you know the lie is going to become very clear the values of this polynomial are going to be very very very different than the the correct one so the the point again with polynomials in other words is that once I force you to tell me a story in polynomials if you want to check that I'm lying it's enough

to check basically at a few random points or even one random point because my lie when it's in I'm telling the story polynomials will manifest almost everywhere all right so that in the second main ingredient in snarks is what we can call homomorphic lis hidden of verifier challenges and before saying what what i mean by that let me say what what I mean by a homomorphic hiding so this is a term I kind of thought of but

then I saw that in the crypto literature it corresponds very closely to these things called kalyan your Maps and graded encoding schemes and this is very similar to homomorphic encryption which I'm sure you've heard the term so so what what is a whole morphic hiding mean well it's some map in E that it has two main properties so one property is that if I show you a of X it's hard to find X from that so that's what that's what hiding means right okay sure you fix it's hard to to compute IG's the reason I call it

hiding and not encryption is that there's no decryption key there's not necessarily a way to get even if you have some there's no key that lets you get from e to X back to X there's that's why I call it hiding instead of encryption so that's the hiding part what is the homomorphic part the homomorphic part what does that mean it means that if I say give you a hiding of X and a hiding of Y well it's a hiding you can't get X or Y but you can get other hidings of arithmetic expressions in x and y so for example I give you the hiding of x and y you'll be able to

compute the hiding of x plus y and the hidden the hiding of x times y smaller I'm simplifying you can't actually get anything like this we don't know so it's going to be some a prime here instead of E all right so what so that's basically the idea of homomorphic hiding now how does this and the idea in our context what this allows you to do is this thing called blind polynomial evaluation well what does that mean it means say that

the prover has some polynomial right so what let's think we're where were we at we were at this stage where we know okay if I force the prover to tell me the story in polynomials it's enough for me to check him at one random point but there's a little chicken and egg problem here of who goes first because if I say to the prover okay I'm gonna check you at x equals 13 what's your polynomial the approver can craft a lie that looks good on x equals 13 on the other hand if the prover goes first he said okay I'm sending you all

my polynomial we got two problems with that one problem is right snarks the S stands for succinct we want small proofs these polynomials of the prover they're going to be huge and the second problem is will lose your knowledge for example in C cache the prover polynomial it contains all the information on the addresses the values of the transaction and so the the kind of the the the clever way people figured out how to how to solve this chicken-and-egg problem is ok the verifier in a sense will go first he'll give the challenge point first but he won't give it in plane for him he'll

give it in this homomorphic li hidden form and what does that do that I'm glossing over a lot of details but basically that creates a situation where on the one hand since it's hidden the prover can't adapt their answer to the challenge they can't choose a polynomial that will work well on that and the specific point of the verifier because it's hidden but on the other hand since it's homomorphic lis hidden the prover can still if his polynomial is P can still compute the hiding of P of s just

where s is the challenge point just from the hiding of s and some hidings of powers of s to be completely to be more accurate how is the time situation I got basically one word slide I'm good all right it's actually a trick if you want speakers to go fast don't show them how much time is left because they'll assume there's well maybe it depends on the speaker it but I'm guessing it made me go a little faster so so that's the the basic idea and I want to tell you one more thing

about so right people call snarks moon math so so where is the exactly the moon in the in the moon math and in my opinion sorry I make in my opinion the the real magic is in these things called elliptic curve pairings which were you know developed by mathematicians who didn't probably know or care about cryptography they cared about like the Riemann hypothesis and proving things about prime numbers and so elliptic curve pairings are where the a lot of the math magic happens these this pairing it gives you this this thing you

you have you know two groups G and what's called that the tart GT and the discrete log is hard in these groups so if I show you G to the X you can't find X I show you g to the why you can't find y but this this pair of groups to get this these groups they have this magical property that you could say kind of partially kind of contradicts the classic diffie-hellman protocol so basically this pairing map what does it allow me to do if you give me G to the X

and G to the Y I can compute from that I can't compute exactly G to the x times y right that would like totally contradict computational diffie-hellman but I can in this other group what's call the target group of the pairing I can in that group I can efficiently compute XY to the exponent so for some generator of this group from from these two guys I can actually compute H to the x times y ok so I think I'll yeah I'll just open any questions about by the way

anything Z cash related or not just the talk okay yep yeah yeah let me go back alright so in this example where alice is paying Bob how hidden or what is hidden about Bob's coin so the sender like Alice will know the value of the

coin and the address of the coin like she'll know it's Bob but this serial number like the way I did it here so for example Alice does know she made this coin so she does know the serial number the 6 to 7 and when Bob spends it in write 6 to 7 Alice will know Bob spent her coin in the real Z cash protocol only Bob knows this 6 to 7 because this 6 to 7 it's actually going to be some combination of Bob's secret key and and the coin so how do I prove that the the coin with these serial

number is on the list like what what proof music a proof to be produced ok so what you have actually is so you have you publish when I create the Bob coin I publish the hash of the coin or a commitment to the hash of the coin and everybody stores this Merkle tree whose leaves are the hashes of the coins and also this list is is public so Alice will prove when when Alice spends this coin she will prove I know some you know

coin such that if I ant some path in the tree such that if I take the hash of this coin that I know in I this path of hashes I will reach this route that we all agree is the is the root of the tree of all the coin commitments and at the same time Alice will prove this oh and that she will also prove and this coin that I know a path to the roots the the serial number or as we call it nullifier of this coin is what I wrote on this list so does that mean that the entire Merkel tree is

an input to the ZK function no so just the root of the Merkel tree so the root of the Merkel tree is what's called a public input to the circuit and the path from your specific coin is a private input to the circuit any other questions hi there um so just came out of that example when alice is sending a journalist proof that she owns a coin that is part of the medical tray how does she creates bob's coin if she doesn't know what the nullifier is

because she doesn't know the secrets so so the the nullifier or what I called your serial number yeah let's call it nullifier is the hash basically of the coin that Alice does know and Bob's secret key so Alice doesn't know Bob's coin Bob's nullifier but she doesn't need she doesn't need to know it it's only important that when Bob spends the coin he will know the nullifier because he will need to publish it and prove that it's correct but an important point here

is that when Alice creates Bob's coin she doesn't actually need to know the nullifier all she needs to convince us is that the value of it she doesn't need to know the value of the coin and that's all she just needs to convince us that the value of this coin that I've dropped is not larger than the value of the coin I've added to the list yes sorry I'm in a bit slow just off the plane but does that mean that just Bob needs to give Alice a bit of information in order to make that coin just his address the coin is basically address value and some randomness that Alice chose to make the hash of the coin more random okay I

think I understand cool thanks we have time for one more question if there is one think you got you mentioned something interesting that coins can have different values and then you can spend coding with like you can transfer it to another coin with lesser value yeah is this exact protocol of the cache yeah so in the actual protocol I can add a few numbers to this list in a transaction and I can drop a few coins to the box and then in the 0 in the circuit I check that the total value of coins I've added to the list is larger

equal to the total value of coins I've dropped in the box is this larger equal actually used to hide the the value transfers because otherwise I could track like if somebody spends exact same amount of coins like I I could try to build an algorithm to track the a of the funds is this used or not oh sorry I think I said larger equaled for simplicity I think it's actually actually that's a good idea maybe to use that for some extra hiding but I think I should double check I think it's actually exactly equal and everything else like goes to the into the transparent pool if there's any change all right thank you very much let's give

Ariel a big round of applause [Applause]