ZK9: A Guide to Teaching Zero Knowledge Cryptography – Thor Kamphefner (Uncloak)

Transcript

foreign [Music] us how to teach some cryptography which I'm actually very very curious about Thor has been working on a project which attempts to do this and I believe it's called hash click right so uncloak sorry uncloak is the the OG in which case uh I think he knows a little bit about this but welcome tour [Applause] and I'm looking forward to Guillermo's later talk about how he reduces it all to linear algebra so okay we got it quicker yeah

yeah so welcome welcome um so I'm Thor for the last several months I've been working on specifically a course teaching cryptography and zero knowledge cryptography to an audience of developers who are sort of looking to do more in ZK development or understand cryptography at a sort of more General level so in this talk we're going to sort of take a bit of a high level but we're going to try to break down sort of the fundamentals of what ZK Primitives are built on take a look at some of the definitions try to make them approachable and hopefully you'll leave this talk with a sort of better sense of how ZK is sort of constructed from a high level and maybe some learning approaches to thinking about zero knowledge as a sort

of topic area so I am cryptographer on Twitter and the project is uncloak and we've been running open courses through our Discord server and posting weekly to our YouTube channel so if you'd like to find those communities you can approach me after the talk and uh yeah let's get started button yeah so who's this talk for uh well this talk bar is basically for I think people who would like to develop CK circuits who would like to understand ZK circuit programming maybe a little bit better Educators like myself since I think there's a sort of large gap of sort of new paradigms to understand so ZK is a fundamentally different sort of set of Primitives than we're usually

exposed to as programmers and it's for the too embarrassed to ask and I want to really thank Guillermo for being both embarrassed and asking anyway so hopefully we'll be able to clear up some stuff and it's for the guy at the party who thinks that ZK is pretty neat but doesn't know how to explain it to everyone else at the party so goal you want to be the guy on the uh left yeah left that's the one and hopefully we'll get you there um now for the starter example like I think that you've probably all seen the starter examples in ZK before but it's okay to kind of wander back through them

and use them for context setting so in this sort of like basic sort of example of like how we want to start thinking about zero knowledge when we're thinking about this is we want to think about like the three definitions of zero knowledge which are completeness soundness and zero knowledge all of which are fairly well demonstrated by the colorblindness example and so as I'm sure at least many of you are familiar the colorblindness example is the prover Bob says that he sees color and Alice says no there is no color there will be no color color does not exist and I need you to prove this to me so the prover says yeah I see color so Alice says okay here are two balls that look exactly the same precisely the same and the proverb says okay yeah I think I

see a difference and so he says no you didn't switch them and so they go okay prove it he says no he didn't switch them she does it again they do this 80 more times and every time Bob gets it correctly of course Alice says hmm well if he was just guessing there was only a 50 chance but if he does it 80 times then he has to get basically 2 to the negative 80 chance of being lying so like obviously we get a pretty good sort of sense that Bob is now a very very good guesser or is probably correct that colors exist and so Alice might be forced to say okay color might be real gur

U um and so to go back to these definitions we have some sense that ZK is the uh is the synthesis of these three properties we have completeness soundness and zero knowledge and so when we're thinking about the context of ZK circuits we're also going to run into these three properties where we want to convince the verifier that I know some program and I've computed some program just as Bob in this context has proven that color exists too Alice and we are going to say come to circuits with this same paradigm so in the context of these definitions just to

sort of expand on them ZK is the synthesis or zero knowledge proofs or the synthesis of these three Primitives or these three definitions completeness is that Alice is convinced by an honest prover that if Bob actually does see color then Alice is convinced that color exists and that Bob can tell the difference um Bob can't cheat and still convince Alice so soundness is that if Bob is lying about the existence of color he can't obviously convince Alice except with very small probability and finally the ZK property is that Alice doesn't really learn anything except the thing that Bob wants to reveal and the ZK property is sort of the hardest to explain the sort of technical

definition of because it involves terms like a simulator but the core of the idea is effectively that Alice learns nothing and so this is sort of like a good example because all three of these properties are fairly clearly depicted with the Waldo example or the cave example they can be a little bit harder I think to to get out um so next we're going to move to something slightly more mathematical we're going to move to schnur's Sigma protocol for proof of knowledge of exponent and in this example I sort of want to demonstrate a more actually applicable zero knowledge proof than I see color and we're going to say that Bob knows the exponent in uh in a discrete log

so as before Bob is going to claim to know something this exponent x in the discrete log problem this is actually a fairly fundamental protocol that gets used in things like polynomial commitments schemes in fact we can take any Sigma protocol and turn it into a convenient polynomial commitment scheme but if you don't know the word polynomial commitment scheme that's okay the sort of core thing to focus on is that we can take this slightly more mathematically involved example and still understand the basic premise that zero knowledge completeness and soundness are preserved by this new protocol and then we can apply that to the context of circuits which we'll do next

so in this context Bob says I know X in some public key capital x equals g to the X and Alice says s before nah and so next up Bob says well I'm gonna have to think really hard about how to demonstrate that I know X but he might come up with schnur's Sigma protocol if you see if you've seen a Schnur signature before this will look actually fairly similar because the the protocol is basically just Bob sends a schnur's signature that proves that he knows the private key but if you don't know schnard's signatures it's really quite simple Bob throws some Randomness at Alice Alice throws some Randomness back and then Bob takes the randomness and

smashes it all together in the element Z where Alice can't peel the secret key back out of out of Z because the randomness that Bob chose lives behind a shield and so it lives behind this commitment where we generally think the discrete log is a fairly useful thing because it lets us say Force Bob to select r without revealing what R is and then get Alice's inputs back and say okay well Alice can verify that Bob is bound to this element and Dallas can verify that Z equals a plus X or ax plus r inside of the exponent but but Alice never gets the secret private key out

so I'll leave this on the screen for just a couple more seconds before I continue nattering but the sort of core idea in this protocol is interactivity and we actually use this core idea of interactivity in proofs despite the fact that we don't actually use interactive proofs in practice we use non-interactive proofs and the sort of way we do this is that most interactive proofs look basically like this where Alice chooses some random element a and if if we can say if we want to enter the sort of Paradigm in which non-interactive proofs are constructed from interactive proofs out the verifier is basically just an abstraction that we

use in fact we can say if Bob can say generate some Randomness from a public Source say a hash function where Bob gets to choose the initial seed then we can sort of say Alice is a convenient abstraction but at the end of the day Bob is just going to treat her as this source of Randomness that we can then swap out with a hash function or a random Oracle a more cryptographic slang so the the sort of core idea here that I wanted to communicate is two things first that we have like this idea of interactive proofs that we can render into non-interactive proofs by treating Alice as just a source of Randomness that we can then swap out with the hash function

and then second the the uh the way that we use hidings in the the exponent is sort of something that we can then expand upon in in commitment schemes which we'll get to a little bit in a little bit so back to the definitions um so when we talked about the definitions for the the color protocol we introduced these three terms that are the sort of core sense of what a zero knowledge proof is we have this sense of completeness that Alice is convinced by an honest prover and if Bob does indeed know the exponent x then he can indeed compute a X plus r and so a convincing prover satisfies completeness in this context

that soundness is satisfied that Bob can't cheat um if Bob does not know X then with only very small probability will he be able to convince Alice that these exponents are aligned because he'll just be guessing at values of x and then finally ZK um Alice would need to break discrete log to actually obtain information about the secret key X and so these are again useful things to keep in mind when thinking about what we're actually trying to achieve when we're when we're when we're writing these CK circuits and so it is now circuit time and Boolean computation

is the thing that we're all kind of used to working with when we think about okay I want to compute a program now Boolean computation is not what cryptographer is like we like Fields finite fields to be quite precise we don't like infinite fields and we certainly don't like floating Point arithmetic but we love we love fields that we can do multiplication in addition over and never have to think about a Boolean operation like an or an and gate and conveniently for us there is a way for us to pretend that that George boole never existed I think his name is George I could be wrong there that Bool never

existed and that in fact we can just treat everything as a an addition inter multiplication operation right so the way we sort of do that is that we say okay well if we take uh if we take the bits b0 and B1 we can just say well and it's just the multiplication of these bitwise elements that's convenient and or is just the uh addition of two bit elements minus their multiplication so we get this very like okay yeah they're perfectly equivalent and the answer to the question can we translate Boolean or Boolean logic to arithmetic is yes and the the the the

etch of Alan Turing here saying nice is a is a gesture to the fact that with Boolean arithmetic we get a touring complete machine but since we have arithmetic that is equivalent to our Boolean logic we also have a touring complete machine that we can do inside of just arithmetic over a finite field by doing this simple translation now um the next thing we might like to do this is sort of trying to gesture at the direction of what are we doing when we write a program and don't don't take notes on this assembly because I kind of scribbled it out and made it up um but when we write our program in a high level language we need to say let's

do some memory operations let's load some value from memory into a register let's do some operations over those registers maybe bitwise operations xores ORS and nands whatever um maybe some addition or whatever we're going to add registers to constant values or other registers and the way that our high level program is going to get translated is eventually going to be into some assembly like instructions right and so in our previous example like the goal was to sort of say well if we have these equivalents of addition and multiplication gates in in ore and and Gates well then we can say instead of

translating these into Boolean logic we can translate it into finite field arithmetic and so now we're starting to see like the direction that that circuit arithmetic is getting us towards is that instead of translating everything into ORS and ands or more precisely from the hardware level everything is in fact a nand gate but that's somewhat a tangent we're going to translate it all into a circuit or an arithmetic circuit but there's an issue and the issue is that if we have say an eight register machine or some number of registers in the machine for each register or for each operation there's going to be a new layer in our circuit and for somewhat Arcane reasons

involving polynomials and multilinear evaluations that we will not get into we really want a short depth circuit so if we have o of n instructions Randy at o of n layers in our circuit that's kind of a bummer because this basically means that if our approver wants to prove something they need to hand an O of n operation check to the verifier so when we actually write our circuits for ZK dsls we usually are writing either we are we are doing basically exactly this we say well let's write our assembly if we're writing an assembly ZK circuit like circom or Maiden assembly or let's write

a high level program that gets compiled to some assembly um like no r or risk zeros high level machines we're going to translate that to assembly it's going to get translated to this not very this this kind of long circuit but we don't want long dogs we want short dogs so we have one trick left in our arsenal when we talk about how can we do everything succinctly because this is what we're trying to get to and we're talking about zero knowledge proofs is this premise is succinctness and that trick in our Arsenal is that we shove everything at the base layer so if we have an honest prover they are going to compute the intermediate values in our circuit and

in fact we can shove a lot of those intermediate values just back onto the base level of our circuit and this means that instead of getting a long circuit like the one that we would have originally programmed the circuit that is O of n in length where n is the number of operations the number of assembly instructions we can get a short guy and our short guy is going to be succinct to verify because it might be only o of log n or depending on our transformation even o of constant time if we do this transformation moving everything onto the base layer and what sort of left here for us is that the things that were really simple for us to do

were arithmetic operations like addition and multiplication and I'm going to just briefly gesture at things that are not simple to do within the context of a circuit the thing that is the least simple to do in the context of a circuit is memory accesses because those are not arithmetic they're not Boolean logic and that's sort of where lookup tables enter in if you've heard that term like P lookup from from Aztec where those sort of enter into the picture is that there are some operations that don't neatly translate into arithmetic operations like addition multiplication and so what we need to do there is we need to say well the prover needs to say here is the ordered sequence of accesses in memory when I store something into

memory it needs to be the same thing when I go load it later and this actually could be an issue because the prover could lie about well if I stored something into memory and I got to the end of my circuit and I really need this to be a three but in fact I cheated and this this is 376. we need to bind the proverb to the fact that this is in fact whatever it's supposed to be so we use a Merkle tree and that's sort of where the circuit arithmetic hash functions come in we need to include in these witness values the W's that have moved onto the base layer we need to commit to a Merkel tray inside of our new circuit down here and this can be the source of like some additional height right because our Miracle tree is going to be logarithmic

in the total number of witnesses that we need to put in and so our new circuit will be perhaps a logarithmic in the new number of witnesses but not linear in the total number of operations that we need to calculate so this is a pretty significant Improvement when we think about what our ZK circuit should actually be able to accomplish but what we win is succinctness and this sort of transformation here is basically that we can change our writing a circuit C of x equals y where our X values were these things on the left we get C of x equals y where Y is some

claimed output of the circuit on some unknown inputs X and we can transform the circuit into a circuit satisfiability instance where circuit satisfiability means in this context the prover had claimed to have some value X satisfying C of x equals y circuit satisfiability is a sort of different kind of circuit where we just need to say does there exist a vector w such that this new circuit which I might have been polite and labeled C Prime for this convenience does this new circuit that we use a transformation for have a satisfying additional Vector W such that the same thing is true after we perform our compilation step from C of X into C of x

w um and so that's where we we sort of do our transformation into r1cs or do planckish arithmetization schemes where we need to satisfy this circuit satisfiability instance then we can compute the values for x and W which is Simply Computing the original circuit C of x equals y that gives us our values for w because our W's are intermediate values plus some extra overhead for the i o operations that I mentioned and then finally when we compute our proof Pi our proof Pi is the sort of complicated step that I I'm sort of alluding in this context because that would be another 30 minute talk but I

will briefly gesture at it the way we actually prove anything in the context of our circuit is that we need to say well the verifier is going to know why but they aren't necessarily going to know the inputs X1 through through xn and we can do this operation row by row over the layers of our circuits and what what is popular what is called the gkr protocol we can take the gkr protocol and say like do this layer by layer evaluation or circuits relating the outputs at each layer to the outputs of the previous layer the final error we need to have the the verifier know something about the actual inputs and that is where polynomial schemes come in so come back to my next

talk and we'll talk about the GTR protocol and polynomial commitment schemes and then finally we have the prover compute the proof pi attesting to the knowledge of X and W satisfying this expression and to go back to definitions we have this model of completeness soundness and zero knowledge well the proofer would never be able to convince a SAT or if the prover actually does this transformation they will always know the intermediate values of the original circuit the W's will always be able to compute the transformation we'll always be able to prove to the verifier that their circuit is satisfied for soundness a cheating improver would need to say that circuit is too hard for

me I'm just going to come up with a bunch of w values and the circuit satisfiability instance will be difficult for the cheating prover to abuse and then finally for zero knowledge if the verifier is attempting to learn the values of the W's the verifier would have to completely determine all of the values that the x's and reevaluate the circuit to obtain these so we get completeness succinctness and zero knowledge for this circuit and that's pretty much it so thank you everyone for coming to my talk and if [Applause]

Google we have about five minutes for questions of anyone has questions for Thor I'll Just Dance while you think about your questions [Laughter] no no one has any questions no ideas no Notions constructions ah there we go all right there's one a brave soul indeed okay and we have a runner so okay so I have a bit of silly question what exactly is w

is the question sorry could you repeat the question uh what is w ah so the W stands for the witness um so when we're talking about looks like the slides are gone um The W is what we refer to as the witness in our original circuit when we say C of x equals y the X values are usually the thing that we're trying to not have to send entirely to the verifier because they can be very long when we extend the circuit with this transformation from C of x equals y to see if x w equals y the witness values are all of the intermediate values and potentially other things too so if the circuit doesn't have a convenient way to say compute the inverse of some element

where we would have to do say the extended euclidean algorithm to compute the witness inside the circuit what we can do instead is we can say include some values in the witness that weren't necessarily intermediate values but are what are called advice values so there are a couple of things that go in the witness first is things that were intermediate values in the original circuit second is things that are advice values that are like maybe the inverse of some element where instead of saying do the entire circuit computation of the inverse we just checked that in that new element times the thing it's the inverse of is equal to one so that's a fairly easy optimization that we can do with advice values and then finally we need to have like I mentioned the the lookup table elements need to have some proof that they are in

fact the the valid transcript of elements of the i o operations so those things all tend to live inside of the witness w and if the proverb has those things inside of his head um it he has computed the original circuit and transformed it into this subsequent circuit where he has these new vectors of values that he can run through this new circuit that we create and this new circuit will be low depth so it will be efficient for the verifier to run their operation the the verifiers time is linear in the number of layers that there are in the circuit so we want those values to be all living at the flat bottom and have a short circuit and that's kind of what we get for this transformation did that help yeah and one more question

on one of the slides you collect the circuits and yeah if you could show yeah so this purple unlabeled is this a sum or a multiplication or some other operation is what a summary multiplication yeah yeah like you have this purple blocks that are not labeled yeah and um so I I didn't put things in this box because I was lazy but ultimately uh I did I did put the equal zero at the top so for a circuit satisfiability uh Gates we're going to be saying well is the addition of in this first left example is the addition of x0 and X1 plus

whatever we put in the witness zero box is that equal to zero and if the outputs of everything is zero then we have achieved our circuit satisfiability instance where we are trying to find some inputs for WS that achieve this everything equals zero argument okay thank you cool we have one more minute if anyone has any last questions if not well thank you Thor everyone give a round of applause