Mathematics Behind zk-SNARKs: An Academic Primer

[00:00:01]hey everyone so um this is working yeah it's working it's just not reflecting okay hey live stream hope you can hear me alright but also um hi thanks everyone for coming to the workshop here at least authority tonight and we've got Mirko who's going to be doing the session tonight the workshop but I'll just quickly say that at least Authority well we care about privacy we care about security a lot too we do a lot of consulting within the security space and then we also do software development too not just the really short bit about us and we're hosting this stuff because we also care about the community helping to have everybody learn from each other learn about the latest advancements with security and privacy and software development and of course that includes ZK snarks and your knowledge Bruce we think that they're pretty cool yeah so we have Mirko here and this is also being this workshop is also being sponsored by the electric electric awning company sorry I keep wanting to call the musique ash but they've changed the name and it's the electric coin company the company behind Z cash and so yeah they also are sponsoring this event tonight - they are users of ZK snarks - so they care - um I guess that's what I'll say about us I now introduce Mirko and probably pass it off to you unless I forget anything good oh yeah yeah the other thing to note is that electric coin company is also the ones who did halo that paper just recently came out it's a really exciting advancements DK snarks and they're on board to do a paper club with the zero knowledge podcast right yeah with one of the authors of the halo paper which to give sure I don't I don't know if I need to give the author's credit but it's sean bo Dara hopwood and Jeff great who are the authors of that paper so that'll be coming up in the future okay that's it for that kind of business now on tamerica Mirko I'm gonna let you introduce yourself cuz you'll do yourself more justice and to introduce the first up to began so thanks everyone who's on the livestream thanks everyone watching you according and of course mostly thanks to you all your present and thank you okay thanks I have a microphone you're good okay so I'm I'm Mirko I'm a mathematician and this is really all that is to say about me and yeah thanks everyone for coming and and things to release Authority for hosting and mostly for doing the organization for this talk this talk is a very basic talk for the for an introduction to the xik to the principle of CK snarks and if it works well we might have an whole series that leads ups to the halo protocol which I personally like very much because it is a kind of recursive snark way which might do a lot of good in the blockchain space especially to solve the bottleneck of transaction verification at some point yeah okay so um one thing I have to notice that this is a workshop not to talk so if you don't understand anything just interrupt me bluntly it doesn't matter so I want this to be a discussion and so really just interrupt me okay so what do we do today and I want you to it we have two major takeaway of this this talk or this is this workshop to have some understanding of what zero knowledge verified computation actually is and we we do this by introducing first an extra three bit security cryptographic steam which I have developed just for this talk it's very basic so we can do all the computation in this gene and then I introduce an over simplified problem which we use as our running example in the snart pipeline and yeah then we just go through it so the snart version we use is a Pinocchio protocol but this is somewhat similar to all the paring based protocols so usually people use growth 16 for this but Pinocchio is somewhat more easy to introduce so the references in the father readings are of course or age sauce here which is the pinnacle protocol itself and from 2013 and as I said the optimized version is growth from 2016 basically he mated more he made the verifier more effective and more efficient and and approval kind of - so another great introduction is this papers it only appears recently why and how ZK snacks works the definite explanation from 2019 I can really recommend to read this paper this is somewhat auto burnout - my approach here and it really goes for all the steps so if you're interested in these things you should read it and then of course there's a companion paper from me from 2018 which currently is just on Google Drive so if you want to read it you can look it there these slides are not online yet and we will publish them later on I think okay so let's start with the question what is verified computing really most of us probably know the public key signatures can be seen as short proof of static data right so you have a data set and if you sign it and you prove the authenticity and the integrity of the static data but in reality we don't have just static data but we also have dynamic computation right thinks it yeah that are dynamic and so the question is can we have signatures for computation really so that you can prove in the end that you have done a computation properly so and if we can do this can we also hide certain details in the comp in the computation but still get verifiable signatures and the answer is yes and of course this is the by now I would say well non-standard names the ZK snark is one solution to this problem which means there are knowledge sucks in non-interacting a non-interactive argument of knowledge so the question is why do we need this and of course there are many answers and I would like to enter this by giving an example of a so-called zero knowledge proof of knowledge and this is you can prove knowledge without revealing the actual knowledge so you prove it in a zero knowledge way so just imagine a task where you have to convince everyone that you know a data set which hashes to a publicly known digest string so we might call this knowledge of pre-image right so there's on the there's some hash value and you claim that you have the data set that hashes to this value of course the trivial solution would be to just publish the data set and I can hash it and both share both hashes equal then everyone is convinced and this can be seen as a proof of course but this is kind of life and some sometimes publishing the data set might not be an option really for example if the data set is a solution to a very very famous problem also you just claimed to have solve it and don't want to publish it yet so a better solution would be to implement the hash function itself not as a native executable let's say on an x86 computer but SSD case narc and then if you implement it like this then you get a proof of the actual computation so in the end you produce a hash value but also a proof that you have executed the function and you can have done this only if you know the actual data set so if you implement a hash function not native but as a Z case narc then you kind of give a proof that you know a data set without revealing the actual data just clear so far okay so then the journal wrote methods that we will start with our three bit pro kleh graphics scheme which we do all the computation in the basic thing is if we use just integer computation we will just ramp up with with crazy long and and very not nice numbers and so then I will introduce a toy example function and then we go through the so called Pinocchio pipeline which is the pipeline for most parents DK snark systems somewhat so we start with the so called algebraic secret and then from the algebraic secret we derive the quadratic arithmetic program or qap for short and then we enter the setup phase where a trusted third party generates a so called proven and verify our key and then we do the actual worker phase well we execute our toy example function and produce the outcome and the proof and in the last step we do the verifier face and verify that this proof is actually a valid proof ok [Music] yeah usually the rules for talks are that you start somewhat easy and then ramped up to big to get more and more complicated to the end so that people at least get the first 60% of the tour but this is unfortunately not possible so we have to start with the most complicated stuff and that is that we have to introduce our cryptographic scheme somewhat so and the pinnacle Pinocchio protocol and basically all pairing based as the case not schemes we require the following things so then we require a finite cyclic group and for those non mathematician in the room you can think about groups basically as the integers with additional so you know from the integers that you can always add two integers to get another integer you have one integer that's doing nothing in the addition that is a zero and for every integer you have an inverse it is the minus integer so to speak so just think about groups like this and then we need a generator of that group and a generator is one element so that you can create all the other elements just from this single element for the integers I think there's none of this but you can think of this s of one because you can generate the five just by one just at one five times two itself you cannot generate the negative numbers here yeah the most unknown power probably is the so-called bearing func parent function which is the by bilinear map we just needed in the last step so it's not really important to keep this in mind right now the basic property we knew it is this one where you can just pull out this exponent out of the function but this is just important they don't so in reality of course these systems are you are usually realized by cryptographically strong pair and frankly elliptic curves this is another group it just says as a bilinear map takes two elements of the same group and then maps it to another group so it doesn't have to be the same it's just another symbol so that we can distinguish this from this functional yeah maybe like that good catch but really just has to be a different group yeah I just want to have all those people who are non mathematician to have an easy example in your heads and you can as an easy example you can use integers with addition but really you cannot use integers as multiplication because then you need fractions and fractions are not integers so multiplication is not yes example it's not psychic but I will give it a proper example here which is our approximately 3.5 bit security system which I came up with this group so this is really everything we don't have all the integers we don't we just have this number so for example 5 and 7 is not element of this so just this number and our group law is this so we just multiply these numbers together like if there were integers and then we take the modulus 23 and the modulus is you divided like in in school like in June of school or how you call it you are divided by 23 and keep the reminder I will do an example in the mod yeah the generator we choose is 2 and now I also will show that this really is a generator that is just by multiplying two ways itself all the time you get really all of these elements yeah and then my non-trivial binding your map I find this and it actually works so I'm cheating because in extra cryptographic groups you cannot do this computation it's consider to be infeasible but in our example you can do it okay us so to get a bit more familiar with the scheme let's do some computation let's multiply nine and thirteen and so as you can see nine and thirteen are really elements from here right so nine is in and thirteen is in Seoul this group is cyclic because let's say you multiply two ways itself all the time then you go through this here somewhat randomly and then you start from the beginning and go through this randomly again and so this is somewhat like on a clock on a clock you have twelve numbers so to speak and you add them and you go around the clock all the time right because elf eleven plus three would be 2 right you go around the clock and so this is cyclic somewhat yeah I will show this in a minute yeah of course because because normal multiplication just forget about this this is not happening here and you multiply the tools together [Music] I will go through an example so the example is here so we multiply nine in 13 and of course you would say hey this is 117 right but it's not because the multiplication is not defined as integer multiplication but by this so you first multiply them like yeah you will see it here so first you multiply them if there were normal numbers which is in 117 and then you divide it by 23 and take the modulus and you see 117 is 5 times 20 see plus 2 it's all the reminders 2 and then the result will be 2 yeah this is a bit a bit tricky but actually it's not that hard you just have to get used to this it's not intuitive in the beginning yeah so I will keep it here for a moment so that you can just look it up no no I think I don't know actually I haven't tested that but it's a generator so it's good enough so and then this is somewhat secret the graphic level because some computation are a heart in this group and then we also need the underlying finite field and in all case this is so-called prime field F 11 which contains these numbers and then again addition and you can do addition and multiplication in this thing but you have to do it modulo 11 so in this case we will go through an example in a minute so addition is normal integer addition Moodle 11 and multiplication is also not normal integer modification or later yes I was thinking that maybe in an example I will go through an example so that's probably better to just look at it so the so the task is now solve this equation for x right I mean we know if these were ordinary numbers then we know how to do it right we would multiply this and then put things on the other side bla bla bla and then we the result and we can because f11 is a field we can actually do it exactly the same way we just have to keep in mind that all the numbers we multiply have to be divided by 11 and then take the remaining well the first thing I do is I multiply this with five so I somewhat resolve the brackets so and then I get to this point right and now three times five is fifteen no it's not 15 three times five is four because 15 divided by eleven gives the reminder of four and four times five is actually nine so we arrived at this point as I said this is the hardest part we just have to somewhat I I also have multiplication addition tables here so you can really you don't have to compute it but you can really just look it up if you want now this is the final few because we use this much more the group will only be used in the end it was fixed by the group and I will explain this in the next slide so now what would we do if these were ordinary numbers we put this on this side and this on this side right and so we arrive here but now the catch is that in the prime field F 11 there's no minus three so to speak and there's no minus nine so we must understand what - actually means and the negative of a number is that number that you have to add to the original number such that you get zero so in this prime field really it means to to get that number that adds to the original number such that you get 11 no I just forgot that yeah it's the same thing yes it's a blend of so then yeah then the negative of three is of course 8 because 3 plus 8 equals 11 and 11 module 11 is zero so the negative of 3 and our prime field is really 8 and the negative of 9 is really 2 because 2 plus 9 equals 11 or zero so to speak yeah and then just I excluded X here and then 4 plus 8 is of course 1 and solve the solution to this equation with kitchen right and so this whenever I do computation the following I do them this way so if you sing how this computation is wrong because it's the wrong number is probably not because I have done it a hundred times and yeah and so this is the relation this proves that two is a generator actually and also proofs by F eleven is our base field because we can put eleven numbers here in the exponent and then we get a repetition here so this is also cyclic right because 2 to the power of zero is the same as 2 to the power of 11 and this is something we cannot do in actual cryptographic roots because it's generally believed that finding the log of the discrete logarithms is hard but we can just derive it from here we just yeah take this and take the logarithm on both sides we don't need it right now we only need it later for the pairing so yeah and this is how you I think about these things as two levels you have the base field at the bottom and then you have the group at the top and you can go from bottom to the top by exponentiation with a generator and you can get kind of from top to the bottom by logarithm yeah I mean I already explained to some what why not use ordinary numbers and the answer is that in groups like G certain computation are much harder even for computers and for example it's generally believed that this equation cannot be solved easily for X okay that's it that's basically the cryptographic scheme and now we have to come up with some kind of computer program which we will occupy and yeah attic Li the most easy one that is expressible in this scheme and so now our computer program takes three elements from our base field and just multiplies them together this is as easy as it gets I mean the the thing is of course you can do a more complicated computation but it's not feasible here because everything is so complicated we will see it in a minute okay so now that we have defined the function we go through the snarky fication process or the Pinocchio pipeline and this starts with the so called algebraic secret or presentation M every finite computer program every bounded computer program can be represented as an algebraic secret and algebraic secret are really nothing but directed acyclic graphs like represent computation so you can think of a graph but the graph has arrows so it has the direction and no cycles are in the graph and then what you see is with only outgoing edges which we might call leaves or sources represent the input values to the computation and vertices with only ingoing edges which we might called call rules or things represent the output of the computation and the internal vertices represent field operation and we only have two of them we have addition and multiplication and the basic idea here is that you can execute in secret so you put the input values to all the leaves and then follow the edges through the graph and then whatever the vertex is decorated with additional multiplication you do that and then you follow the graph until at some point you enter the roots of things and the basic point is that usually in reality you don't have to come up with a sequence yourself this is most like if we program a normal computer program we don't write assembly code right we write higher-level code and it compiles down to to assembly code and in snark it compiles down to algebraic sequence really yeah and yeah something I want to notice the different compilers give very different secrets secret of representation and compiler optimization is important because secrets are not really made for computer chips so the execution of a secret in reality is really slow and when you have large secrets that's considerably slows your computation and should just give a reminder this is not an actual stock sequence just some picture I took from the internet to remind people that this can be can be very complicated right actual secrets look a bit like this so but not ours for our functions the secret is pretty straightforward and just or we can just represent it like this but it's not the only representation we can represent it differently or arbitrarily complicated but this is one possible representation so we put the input values X 1 2 3 here and then do the computation so whatever we put here we multiply it with what we put here to get this and then we multiply this with what we put here and then we get the final output right so this deck happens to be a binary tree but this is just because of our example is how it looks in general okay so the point here is that we have to multiplication gates and the most important part is for what follows is the the that every edge gets a label and this led the set of all the labels it's really important to you and we have somewhat distinguishable labels so we have labels that are related to input and output and labels that are related to middle terms in the computation yeah one could use addition but addition is somewhat handled differently in z.k snacks actually as I say addition comes for free because addition does not add to the complexity of the system and if I would have used one addition gate here then things wouldn't work out so I really was forced this is the basic example it's it doesn't get simpler than this one but you have to use at least two multiplication guides for this to work so the next step is what are assignments and an assignment in general just associates feet element to all edges in an algebraic secret you know the edges were labeled so we represent every label with a number so to speak and but the major point here is that an assignment is valid if the field element really arrives from executing the secret and all other assignments are called invalid and the first major off shop shot here is that valid assignments of proofs for proper secret execution that is yeah maybe we just go through our example you know as we can see here this is a valid assignment because we have the input values two three and four which we just put in here here and here let's say and then we multiply two and three and this is six so this is valid right and we multiply six and four this is of course two because 6 times 4 is 24 numbers and it's over minus 2 so this is a valid assignment all these numbers here check up if you really execute the circuit to give a counter example a non valid assignment here would be to have the same input values but then here appear 7 and here P is 8 and this cannot happen if you execute the secret right because three times two times three is not seven and this is no narrator so we have valid assignment and invalid assignment yeah of course for every input set you have you have a different valid assignment you can choose different input sets here I think that would depend on the actual circuit in this secret because if you if this number is determinated and this number is each other with this number is there's only one possible choice here yeah there there might be other examples I don't know that might happen yeah yeah because no there's no security in here really right now because this is done in the finite field and it's generally believed that in the finite field or computation are somewhat easy after that we go to the group and there things become smaller and yes this is to just appears because we do the computation in f11 six times four is not - it shouldn't it really shouldn't yeah I have I this is our secret this is our secret so I have to find what are these this is our assignment in one always means this edge nothing else so a question on the livestream is is this generalized to any computation in the Turing machine in the Turing machine it's just generalized Liza bill to any computational Turing machine I don't think so I think this is not your incomplete and I'm not the expert here but I think the general rule is that you can only represent bounded computation so you don't care you don't represent infinite loops because then you would have infinite graphs so a bound computation is a computation that terminates so not an infinite loop right because you have to unroll the computation and then transform it into says you say yeah I think you don't have to go that far you just have to prove that your computation is bounded somebody but this is not so much my expertise so the off short here is really is add valid assignments are proof for proper secret execution because if you have the valid assignment and you must have done or at least someone somewhere must have done all the computation at least a single time of course you if someone does it a single time you can just share it and then everybody can run this it does it's not really a proof for proper execution but it's a it's a major step forward so but this these proofs are not short if I send you a valid assignment and you have to to verify the proof you have to do all the computation again and then you say oh this is a valid assignment by a but I have done the computation so I could have done it in the first place with really no point this is not a short proof or something and so the major step now to get short proofs is to transform a circuit into a so called quadratic arithmetic program and the quadratic arithmetic program of a circuit it's really nothing but a set of polynomials really so and you can think of them as building blocks to encode secrets into a polynomial T and assignments to sequence into a polynomial P and the first major point is that the polynomial your pee you get from assignment is divisible by the polynomial T if and only if the assignment is valid that is if you have a valid assignment and this equation holds that is there's another polynomial H such that this equation holds and if the assignment is not valid if you just made it up then the polynomial you drive P doesn't hold this equation but still this equation is really complicated because you have to think of these polynomials it's it's really huge like you they have millions of constant or something so these are huge polynomials so if you divide P by T this is also a very complicated computation so it's still not short ya TT will be fixed later on when we compute the QEP than t is a system constant it's part of the surya you can derive it forms for the circuit and it's a constant because we have the circuit and the circuit is enough to prove that you have done the computation but it's not a short proof if I if I get a valid assignment from you and I want to verify that this is a valid assignment I have to recompute the whole circuit and so I have to do the same same amount of work it's not a short proof and the whole point of snart's is to get short proofs no T is fixed for the circuit but you can later on generate different proofs or different people but the different different proof of keys are mean for different people yeah this is the next step I will overcome so so still as I said this computation is really hard but but the second major point and even the whole idea here is that was overwhelmingly high probability this equation can be verified in single point so instead of really doing the polynomial equal equation you can just do this and these are field elements so this is really short so you go from something really really big to something really really short this is just one test and for polynomials is is good enough because two polynomials can only share a finite amount of points they never share an infinite amount of points or something so of course you lose some some degree of confidentiality but it's still very very high the probability but on the other hand you have to make sure that the point s is not not not not known so you have to have someone which come up with this point s and then later it deletes it so we need to trust itself party for this now you just check for one point because there's really probability speaking not much of a different if you check for one point or for ten trillion points or something the point will later be chosen by the trusted third party as a secret and then they set up some stuff so that other people don't have to know the point and then they are hopefully delete the point so no one knows the point anymore this is why we have to have a trusted to a party unfortunately for this protocol but really you can imagine how much of a step it is from from this huge computation to this very small committee so it's maybe in some some system is squirt but the trusted supplier so how do we compute the cue IP then and now the QAP is a set of of polynomials a fixed polynomial T and then these polynomials V W and Y and okay so to derive the Qi piece what we first do is for every multiplication gate in the secret we choose randomly one element from from the base field why is it random always an element at all why not there's no reason we just need a bunch of element if you don't have to compute them randomly I think it's not really the point I sing it I wouldn't hold my head for this but I think it doesn't matter yeah choose arbitrary elements okay because you don't want to cryptographic randomness okay it's an arbitrary would even be better yeah yeah this is the number of multiplication gates in your circuit addition gate don't count here they come in for free SSA but for every multiplication gate so you have a big secret you have million multiplication gates and you have to come up with a million random or arbitrary elements this is also a question I don't know and even the question is do they have to be invertible can I choose zero all the time I don't know it's not specified in the paper and would be interesting to do more research on that so once we have choosen them then the target polynomial T is really computable pretty easily so it's just effect multiplication of the zeros of a polynomial so to speak which has the zeros of this set yeah so in all case we have to choose two elements and then we built e like this but we will come to this in the example in a bit yeah and this is somewhat non-intuitive but it's not hard I will just go through it and then we will do with the example and then will you get the point but this is really not I wasn't able to explain it really simple so the polynomials we will here represent left inputs to multiplication gates and the polynomials W represent right inputs multiplication gates and the polynomials Y represent outputs of multiplication gates so to speak right so all polynomials from or a polynomial from reindex by this by the by the etches is one at a multiplication gate if the edge is a left input to that multiplication gate and zero otherwise and similar the polynomials from W is one at a certain multiplication gate if that edge that index that polynomial is a right input input to the multiplication gate and zero otherwise and the polynomials from from Y is one at a multiplication gate if that H is an output of the multiplication get in zero otherwise yeah this is it's really it's just crazy to explain now I will do it in a second and then the off shot here is that from from this polynomials or from the q IP and a valid assignment so if you have a valid assignment you can generate this polynomial okay let's go as well example and to make this more clear so as you can see in our sacred we have to multiplication gates right and so I we have to choose two numbers and as it so happened I choose five and seven for this which I now prime feared right I cannot choose 13 or something but life until well then the target polynomial is really easy it's just this equation and I insert five and seven here yeah so what's what's the what's minus five and nine in F eleven six air n minus seven right right good great so and then I multiply this and this is in our target polynomial and so we have to come up with these polynomials and okay so we have to apply the Pinocchio rule and really we go through through all the edges here right they are they are indexed but all the edges and the rule is that if the appropriate edge let's say in 1 and this example is a left input to a multiplication gate then the value has to be 1 at the choosen number so because this edge is a left multiplication K 2 N 1 the polynomial at the number we have chosen for M 1 has to be P 1 and because it's not a left input to this multiplication gauge right it's just here the value has to be 0 and so in 1 here is not a left input to any multiplication gate right it's right input to this multiplication gate so on both multiplication Gator polynomial is defined to be 0 and these are not the polynomials yet these are just equations from which we can derive the polynomials and the same goes for n 3 so in 3 is not a left obviously not a left input to any multiplication gate so both of them have to be 0 but now MIT MIT is the left mood left input to the multiplication get em to but not to M 1 so this is the defining equation for this polynomial and then last last but not least the output of course is not a lefty input to any of the multiplication right well that's the rule and the same goes for the right inputs so of course this is not a right input to any multiplication gate while this is the right input to M 1 and this is the right input to M 2 this is not a right important this is also not the right input so I think this is somewhat clear right and the same goes for the Y so the rule here is that it has to be an output and of course these are inputs so none of them is an output all of this is 0 this is an output from M 1 but not an output for them to and this is now tough for them to how these numbers came up now so these are not polynomials obviously these are equations but we know from mathematics that a polynomial is defined on certain points completely so if you have a polynomial of degree N and you have n plus 1 points then it's completely defined on this and so we have two points right we know that whatever this polynomial looks at the point five it has to be zero and if the point seven it has to be zero too so what we really do we have specified our polynomials on five and seven and the only polynomials are determinate it on two values are really linear polynomials so in your function in reality of course these polynomials are much more complicated but yeah our example is sort of a simple one so so of course I don't compute all of them right here in front of you so just go through the example of the in one polynomial so it is a linear function and it's determinated on to two values here so we just plug in this value and this value here which is this right because it's a left input to this but not a letter left input to this as I said and now this our two equation is to India terminated so we can use basic Gauss algorithm or whatever to come up with the solution as a solution in this case is five and nine and so our input polynomial and here's f is 5x plus nine yeah you can yeah I don't know I mean I think most people just use the leg motion interpolation to do this but as I said this is computationally expensive and I think this is one of the hardest part in the overall generation of the setup phase would be great to have something that will speed it up but at least it's a one time job right you just do it for once and then you can use the computation over and over again so I did the computation and this is you know these are the polynomials that showed up here so really if you go through this at home or something you can see that this really reflects left input to see or whatever and this reflect the right version and the output burden and then our QA P is just a set so it's a target polynomial and it's a set of left inputs a set of right inputs and a set of outputs and so yeah what's what's really the point of this the point is that we want a polynomial P that is divisible by this polynomial if and only if the assignment to the circuit is a valid assignment right and you can you can build it like this and I cannot go through all the details of the proof that this is really divisible by T if and only if it's a valid assignment but the intuition is that these really represent left inputs and these represent right inputs and these represent outputs so if one is a left input and the other is a right input and you multiply them because this is a multiplication gate and what you get is the output then this is their rule right and so the polynomials have to be defined in a way such that this is separated for the multiplication gate so to speak so the polynomials only one it one of the multiplication gates okay so let's do our valid example you know remember this was our valid example and then we plug in everything here we plug in the polynomials from the table which unfortunately accounts show right now and the coefficients here from the valid example and then we get this monster and just computed down blah blah blah until we appear here and so s it so happened in this case a polynomial is really the same as T this is the next accident and really I was just too bored to do the computation again with other numbers so I just kept with it this is of course divisible by T because it's equal to T and so it's of course divisible if we do the same thing with a non valid example like this if you know you cannot be a five if we have the same input values and here can't be a nine then we come up with this and do the computation and this is our polynomial and when we do polynomial division to check this we add this just so it's not divisible by T because there's a reminder and so it's okay so this is really the point right so if you were a worker that had the secret and that execute the sacred then you are able to come up with a polynomial that is divisible by t TS t cetera polynomial in our case is this one that's a good question I mean the way P is set up is that you just move P is just multiplication of everything that comes from the left and everything that comes from but just multiplication not addition so I think that it's y addition comes for free but really I can't say in detail because it's it's yeah it's exhibit of polynomials not quadratic right but it's so to speak yeah you have to multi P of multiplication so you quadrate polynomials so to speak I think that no multiplication gates cannot have three inputs addition gates can have and even in the pin occupy but there are some additional gates develop which has more than two inputs let's keep it because I'm not very very qualified to explain the details okay so the next step is that we need a trusted set up faces so we need some some party that yeah so basically the Pinocchio rules say that the V's are left inputs to multiplication go to a certain multiplication gate this one right yes that clear okay that's the point okay so the qrp is a cryptographic scheme and the secret is not public knowledge it's just somewhere on the internet and now we need to trust a third party and this trusted third party has to come up with a bunch of random elements from the from the base field so of course the same question goes here right I have to be I think they these values have to be somewhat random because you should not be able to deduce him in whatever reason because they are really later called the toxic waste and then the trusted third party comes up with a so called prove okie which the prover needs to generate the proof and with a verifier key which the verifier then later needs to verify the pool yeah and this party has to be trusted so it's a party because we have to trust them that these values are the later later on because in this for example is a secret point where the polynomial is evaluated on and so yeah we have to drop this party that the elements are deleted and as most of us know no Z cash went through this whole ceremony to do this okay and then the proof of key looks like this we have our generator right and then we have we have this so it's really a set of group elements used to encrypt the non I all related part of the polynomial P and as you can see these are just indexed by the by the mid terms so in our example this would be the input and output related elements and we are just have one middle middle related but eh so to speak so in our example this will be really easy but for every edge that you have in the middle of the computation that is not related to input and output you put one of these elements into the prover key so the prover key really depends linear on the number of internal edges and this can be seen as a drawback of the of the system because poovu keys can become really large like in the Pinocchio paper there are examples equal for the prover key has gigabytes like five or so gigabytes of science so because when you have a million of internal vertices and you have them seven times a million of these elements already so these these elements really later we'll check the polynomial P and these are additional security constraints I will not go through this because some of this has to be was optimized the way already in the growth paper so we will just leave this like this and of course approval key is not unique as as you as you asked previously you can generate different prove our key because you cannot come up with a different set of toxic-waste elements and that the verifier key is somewhat the the competition of this these are here's the target polynomial encoded evaluated at the secret point and this really encodes the the input and output values of the circuit and the same goes here saw it also Rises linear in the number of input/output gates so if you have a computation it has a lot of input and output case then the verifier key would be would be large no really yeah this part I skipped completely because it's already soft somewhat in the graph paper okay it's not really good so I know yeah this is these are the random numbers that you have to choose they have parts of the toxic waste yeah so in our example we just took this random number so we just go nine eight seven six five four three two and then we compute this additional number here right I mean we have not much choice choice we just have yeah this is the multiplication in the f11 so now we encrypt these elements so we have choosen these elements and now we encrypt them by putting them in the exponent of our generator so now we get group elements reading right so yeah we how do we do this I mean in our example we can just look it up here these are the generator rules and then you can just skip through this and do a computation you can do it by hand that's maybe a shot just 2009 a foot six in the other cell so in our case approve a key because we only have a single middle edge so to speak we only have a single Miller's also approve a key will particularly look like particularly simple and so we really look up our quadratic arithmetic polynomial and then look up the the mid part and insert our secret evaluation point seven into this and then we get this yes seven is the secret value choose from the toxic way so it's part of the toxic waste and this is the point where we evaluate all the polynomial set so instead of using the actual polynomial we'll use the polynomial evaluated at seven in in all our example now we choose seven as part of the toxic waste so here the seven really is listen it's it's also for them too right you're right but this just happened it's just just happened because we only have 11 elements so it will happen yeah so with we insert C polynomials and then it's just a matter of computation blah blah blah and at the end we will derive our prove a key which in our case is this so it's just a set of group elements really so as I said if we had more middle edges like millions or so then each of these will not contain just a single element but each of them will contain a million whatever it is so this would close very fast and the verifier keys the definition is this one because we have now for the prove okie we had just one edge but now we have more edges we have three input edge so in 1 or Pradesh so this it's considerably this one just forget it I just not deleted it so this isn't it's not it's not there yeah and then again we look up these polynomials in the queue IP and do some computation and then we'd arrive at our verify key here really so if you want to know how this is done then probably should do it at home as an exercise because it's just this is just too much now of course the verifier key is related to the prove okie right if you would choose a different kind of toxic waste then you would generate a different prove okie and also a different verify okey so prove a key and verify our key really comes in in pairs and these pairs are often called common reference string and so in our example this would be the common reference string of our qap and of the sacred CF right because we could have choose other secrets for our function and other qap yeah to distinguish it from random reference for common random string or something yeah so that's the set up case we've done now and what's now out there and the public is the actual problem the circuits the qap and the common reference string though this is just out there and someone now might take these things to do a computation so and the task then is given an input sent given an input set Ian executes the secret to compute all the intermediate values this is important and also the output value of course an ordinary computation you are just interested in the output value but really when you want to prove proper execution you need all of this yeah so so proof generation works like if you if you have done the computation then in the end you get a valid assignment and you can use the valid assignment and the QAP to compute the polynomial P and the first step what you do is you divide P by T and then you get this polynomial age and because the assignment is valid and this division works so to speak and then you use the proved okie which is public knowledge to compute this proof and this proof is really really amazing and what what you do here is you sum up all the parts that are related to the middle to the middle stuff of the computation into one element so no matter how many steps there in the middle computation one or a million everything just sums up to one one element and so the proof really has constant size so this is great in in the actual preoccupy path the proof has 288 but no matter how large the computation is I mean the off shot is you have large proof of keys and large verifier keys but the proof actually is a constant one so you basically only have eight elements of the group because everything that happens in the middle you just compress by linear combination evaluated at a certain point and put it into the group and that's that's your proof well yeah you can say that P knock you really has short proof none of the yes no they're all knowledge so far this is additional things you have to check to make this a valid proof but as I said with all that goes through this because gross already simplified this down to three three things not not eight this although yeah so one thing to remember here that this might look easy but it's actually not because the prover doesn't know the secret element here so even if he can compute this and he cannot compute the evaluation at the point s because he doesn't know s as a secret so the question now is how do we actually generate the proof without net it and knowing the secret value and I think that goes into this you know what what he's doing is he basically used the exponential loss right so multiplication and the group is translated into addition into the exponent and multiplication in the exponent is done to exponentiation in the group and so for example if the prover wants to compute this and he only knows this from his own computation what he can do is he can compute this because this element here just this one in the bracket this is part of the provo key and this comes from the actual computation and then you just have to multiply these things so you don't have to know the secret value all you need is approval QED and all these elements are the Pavo key and if the prover key is very large this gets compressed because you just multiply it down all the time so in our example again yeah we be unfortunately I don't approve okey yeah so you gotta take my word for this somewhat so the middle index from the from the proper execution was 2 times 3 remember so this becomes 6 now we just have to put this into the exponent here all these numbers here are part of the prover key already so we just have to take these elements from the prove a key and then exponentiation to 6 and we can use a lookup table and so we generate this proof for our computation so giving input value 2 3 & 4 and alpha value - this is a proper proof that we really have multiplied applied three numbers to get yeah so this is it now the prove our generates the proof and he published the proof and the Pinocchio protocol is so-called public verifiable protocols so everyone can check the proof now and this is called the improve verification so the task is that given an input set in and an output set out and the proof P verify that the proof is correct so and then remember that the whole point was that if the prover has executed the computation then he knows the polynomial P that is divisible by T right and we don't have to check this but we can evaluate this on a certain point and for us all so it's important that P is not just some P but it's a P that is alleged from those input and output values and we can check this really by doing this computation and you remember that B is the pairing function yeah we'll go through the example now and this is something the verifier can compute because these are the polynomials X related to the input and output values and this is coming from the proof so this is what the prover has done and the same here so this is this can be computed by the verifier and this comes from the prover and this is part of the very fine key and this the proven else is a polynomial age width which is a divisor of P 80 so this comes from the prover and again this can be computed by the verifier and this comes from the Pula so every the verifier shouldn't have everything in here now and also the Pinocchio protocol especially needs to do this computation we won't do this as I said and this is optimized by the growth paper the problem here is that this paring function is usually very slow on cryptographic curve so if you want a fast system then it might be advantageous to to drop this to us as little element as possible yeah you can also use a fantasy metric pirate functions so I think there's a proof that you cannot reduce it to just one pairing and the grass paper I think reduce it to three pairing so it's still a topic question if you can reduce it to two pairings but so um let's see why why does this prove that p is divisible by T and this is somewhat the most complicated part of the talk so let's just try to get this so as I said the task is to verify that P equals T times page for some polynomial agent we can have a sextant version of this so we can do this at a certain point on you right and also if this is a group generator then we can do it encrypt it so to speak in the group so the task really is to check this and the point is here that I want to show that this really is just this and this is what the proof was doing that the verify is doing right okay so how do we do is we do we just so we want to prove this right and so we just defined this as this and then we go from here to here right we just in insert this into K and then we get this one so now we use the properties of the pairing function that is we can just take this and this out of the exponent and we do this on both sides and then we come to this step and of course you can say hey wait a minute this is not not known this is forgotten and so we cannot compute this and this is true but this is just a principle mathematical explanation while these two things are the same so we don't really need to know to know them okay so now we replace the definition of P of s by the actual definition of P here which is the left input power times the right input Pyatt minus the upper part and this equals n this again that's all we do some some group magic because this is a minus this really means that it's the inverse of something so we can multiply with the inverse and put this part on to the other side yeah and then we can just use the the properties of the of the pairing and put this into the first one this into the second one and so we arrived at this one here and this already looks like somewhat something like our proof so we use exponential loss and take this one else and this is all our equation so but the verifier went the verifier really compute this what what he is really doing is he's checking this equation so that's I think it's the whole point of the DQ snogs so it's last but not least let's go through this in our example and really unfortunately I can't show it so I really just put everything plug everything in that we have so far and we get this so one times twelve this is the neutral element so this doesn't really change and we we plug this in here and then remember the definition of our pairing function which is this one and now we can look up the base two logarithm but anyway so if you would have looked this up then this would be like this and then you multiply it and the exponent in the end you really get to two equals two in our scene so this means that the verifier has verified that the proof is an actual proof hmm would it be safe to say that the key result from this I think this is also a shutoff of this paper because you use the binary pairing to verify proofs but I think as far as I understand the brushed paper optimizes because here you have 6 or some more pairings and then the gross paper you only have 3 so the Rost paper makes it a little more efficient I think the cue IP and everything that follows from the QRP is somewhat automatic really the optimation part comes from deriving the circuit from the from the original program ok so then last but not least maybe let's have a word on their own knowledge so in our computation we had 3 input values and we just proved that when we multiply this we improve Ellison we get the proper output value but at some point a proven might not want to publish his input values so what can you do and the point here is really that we have to extend the verifier key by this this is not so important for now the really important thing is that we expend the polynomial P by some random numbers like this so the worker generates through random numbers and then exists in this in this to the polynomial P and now the worker is free to choose where to put this randomness and so in our example let's assume that the very that the prover wants to hide this first input value so he the the worker really says that hey I know one number that multi price was three and four such that the result is too but I don't reveal that number so what he can do is because this is the left input he can take this randomness and just add it to the appropriate value here because C in one isn't the number he wants to hide so he can put this to the C and one and so now this is not the actual number anymore but it's the actual number plus some randomness and so the number is scrambled you cannot reveal the number anymore yeah you blind import value by but I did adding it to a random number now let's suppose he wants to to blind this number and this number let's say so he wants to blind to two parts of the right input so he can split this into two and then at half of this to the first and half of this to the second and you can really do this with an arbitrary amount of number so you can really choose which numbers you want to hide and you can even do it with the output at some degree this becomes trivial because at some point you can say hey I know some bunch of numbers with do some stuff and we'll give some output so everything is their own knowledge but really in our computation for example if you want to hide all three numbers then what does it really mean it means that I know three numbers that multiply to 2 but I don't reveal which number yeah then you have zero knowledge of zero knowledge I don't know you know you know how to do stuff yeah but you can also somewhat randomize the proof itself because you can put some of this randomization into the middle part and then you have generated random proofs which which so every proof is different from I think the degree of obfuscation is perfect it's zero knowledge you cannot have more fiscal you can have as much affiliation as you want because you can divide this randomness into arbitrary amount of randomness yeah but this should be random right yeah because here you're just has halves one randomness right and you in principle you can just edit to one of these but if you want to add it to two of them and you have to split it in part but randomly split it by half is also randomness so you can split it in arbitrary amount of times yeah and that's it yeah so one thing I want to say because at the beginning I started with the example that if you stock if I a hash function let's say a char two then what you get in the end is some way to prove that you have a pre-image of a hash function but without really revealing the preimage so this is how you do it right so we will just scumble the preimage and then publish this but it's not an extra preimage but syria for proof that this if it were the actual preimage not sacrifi it or not zero knowledge defied we also want to play in the engineering games yes this is yeah definitely definitely but there's this yeah you can do this easily yeah then it's sorry but that's not showing complete it's I think the official term is alpha turing-complete or something because you cannot encode infinite loops that's the only thing that you cannot in this is in the simplicity paper which is a great new language for smart contracts you should look it up and in that paper this is explained because simplicity is not truing but almost Turing complete language block stream doing okay yeah that's it I don't know this is not really wheezes I don't know I can only give a trivial answer because degree doesn't appear here or at all right so stocked it's nuts not snacks right it's a completely different approach yeah that's it yeah this I can't say much about this I hope that if this works well and people like this talk then we can go through additional steps next step maybe will be the bulletproof protocol and the goes through steps to a to arrive at the holo protocol in the end and then have a good talk about because of