# ProgCrypto (ZK) Study Group 2025 — The Moonmath Manual to ZK-Snarks: Chapter 8 ZK Proofs - Channel: [Ethereum Malaysia](https://streameth.org/ethereum-malaysia) - Date: 2025-10-09 - Duration: 45:54 - Watch: https://streameth.org/watch/yt-OV3KD06dO70 - YouTube: https://www.youtube.com/watch?v=OV3KD06dO70 ## Description It’s that time of the year again—We're diving back into zero knowledge proofs! Join us for a weekly study group starting June 24 (Tuesday), as we explore the Moonmath Manual by Least Authority. Each week, we'll break down the theory and optionally implement what we’ve learned to build real understanding. Whether you're new to ZK or looking to solidify your foundations, this is a great way to learn together. ## Transcript Okay, great. Welcome. Uh, and yeah, as usual, let's start by going through each part and if you have any questions, stop me and um, yeah, ask it um, either in the chat or you can open your mic to ask and yeah, we'll go through your questions. If not, we'll go through the entire thing and then maybe go through some of the more interesting parts or parts that are a little bit uh, more complex. So, without further ado, let's go. Chapter eight. So let's start from 8.1. Any any questions you have got when going through this okay I suppose there's no questions. Uh you can still write in the questions in the chat afterwards when you think about it. Uh let's go through chapter two. So, graph 16 protocol is the main topic for today. Um, any questions? Setup phase. Prove her face verification phase. proof simulation. Okay, so that's a very quick run through. Um, okay. So, I'll go through some of the parts that I think are quite quite interesting. So, again, ask questions if you have any. Um, yeah, it's meant to be a study group and all. Um, so yeah, anyways. So um yeah proof systems um let's talk a little bit about proof systems. So it essentially proof systems are well systems that allow you to generate some zero knowledge proofs uh in this case right it allows you to so usually involves approver and a verifier and there's an exchange of message and this exchange message usually involves you like the approver wanting to prove something and generating a proof for the verifier which then verifies it um using um the cryptographic primitives we introduced in this book. Um but yeah um there is like a more um more formal explanation of this which is this. So let sigma be an alphabet and L be a formal language define sigma there is then a proof system language L is a pair of probabilistic interactive algorithm PV pro verifier. Yeah. So that that is is what it is right and usually we want completeness soundness and of course zero knowledgishness uh in this case and um I believe we briefly went through what those are in the first um session. Uh but yeah so um yeah completeness you know if the word is in the language for both prover and verifier verifier accepts if the string is not a word in language and verifier proto follows the protocol verifier puts reject um and zero knowledge um verifier learns nothing about x other than x is so in this case x is some word um other than x is in the language a set l right and so Yeah, there's also the difference of non-interactive and interactive. um suck and usually we'll we'll talk about a lot of ZKP as um we we refer to a lot of ZKP in a lot of the proofs a lot of ZKP protocols actually um a lot of proof systems actually are succinct um um ZKN stands for zero noise succinct and non-interactive argument of knowledge that's why a lot of them is is succinct uh when we call them snarks um yeah that that's where it comes from that's also why a lot of the modern protocol um uses CKP as a way of compressing um data. We see this a lot in roll outs and all. Yeah. So yeah, here we go through a little bit of what prover and verify algorithms are and yeah that's it that is generally what proof systems is. Uh in a proof system there's a prover there's a verifier and you know proer wants to proof something verifier wants to verify something both wants to make sure each other are doing the right thing essentially that's essentially caps questions I suppose not um let's go to 8.2 to graph 16. So in graph 16 um I'll go through a few parts. Um again please if you have any question when going through this pick up um anyways so um growth 16 well um first of all we need to understand growth 16 um to set up this proof system. So gross is approved system and it's built upon um well it depends on the implementation but it it's um built upon pairing based cryptography and um it uses um forgot the curve it uses but yeah it uses p pairing friendly curves and um it's it requires a trust setup. It's not trustless essentially. Um so yeah that's that's what Graph 16 is. It's one of the earliest proof systems out there. Circom uses Graph 16 by default. They also support Plon which is like a newer version of uh proof system. So we'll talk about later but yeah so Graph 16 um when we set it up we require something called trusted setup. We'll talk about it in more detail later. Um but yeah so let's talk about it. So um so G 16 recall we have something called R one con system and R1CS right so R1CS is essentially um something defined over um that that we talk about when we talk about circuits we talk about representing the program in uh circuits itself. So RNCS allows us to convert programs into um well essentially polomials and then we'll also use this RNCS to generate something called QAP which we can then use to uh essentially um well it's better used in in proof system itself. So QAP um are a polomial that represent or that that encodes um what we have in RNCs it's well in a way it's the interpolated form um you usually do an interpolation on your RCS and then you get a QAP of that application both of them uh a form or like they are they are essentially your application into like converted into polinomic Right. Um we convert it to RCS first and then we convert the RNCs into QAP which we can then use um for our next step which is ZKP generation. So um G 16 well uh there is a few parameters we need um to to in in a G 16 protocol. Um here it is. So R, G1, G2, E, G1, and G2, small G, small, small G, right? So here R is just the order of the field that that of the group essentially. So this this is affected by your elliptic curve obviously, right? Um but these two are the finite groups. So um G1, G2 are two different finite groups of order R. Um this is a pairing bilinear pairing. computable between G1 G2. So there uh G E G1 G2 mapping to G2 or what mapping G1 and G2 G to G2 G1 and G2 into G sorry. Yeah. So essentially it's a non degenerate pairing for some target group G uh that G1 and G2 will map to. Um this is what E is paragraphs. Okay. Uh G1 G2 here are just generated for the G1 group and the G2 group. So this is what we need in order to start using graph 16. And so in the graph 16 protocol there's uh multiple steps. The setup phase, the approval phase, verification phase and the simulation phase. Uh simulation phase is uh mainly for us to reason about um the if I'm not wrong the soundness of the protocol. Um you basically use this to show show that uh to a certain extent extent to show that uh without the secrets you cannot um generate a false proof. You cannot generate a fake proof. Yeah. Um yeah. So in in in production or like in in actual use case usually we'll look at um these three fake setup prover and verification. Okay. There's an example here for the R1 factorization problem where essentially this they provide the uh the variables here and uh yeah this is essentially it right order of 13 G13 G23 E the pairing pairing itself um this is uh G1 generator for G113 this is generator for G213 um yeah that's essentially it okay so setup phase so set phase is one of the more important phase in any um well in any proof systems that require a trusted setup and uh in in our in this specific case. So in in the case of crop 16 uh notes that uh we need to generate we need to have a setup for every um well here is for every RNCs systems right that means for every program you need to do a setup phase. Um there is a need to emphasize this because uh it means that every time you write a new program you need to do setup and setup usually is a very expensive step um because uh it requires you okay it's not expensive so to say it's expensive because we usually use um MPC multi-party computation but um it's usually a very um trusted or a very a very critical step to ensure the safety of your protocol. Um, so there's a need to emphasize this because in a real life scenario, what this means is every time you write a new program, you need to do a setup and every time you do a setup, you need to take care to not up. Forget my forgive my language, but yeah. Um, so yeah. Um and a lot of modern um proof systems they either go about fixing this actually um a lot of the new ones new new proof systems actually come about to resolve the problem of this um circuit um required circuit truster setup right per circuit trusted setup or per program trusted setup. Um what they do is they have something called a universal trust which means that you can just generate your CRS. U we'll talk about CRS later. You will generate like a like your secrets your stuff. Um you you do a trust once and then you can reuse the same thing for any program that is um that that is compatible with with the proof system essentially. Um yeah. So that's why we are mentioning this here. That's why we we talk about um this specific thing um in this case draw 16 requires a trust setup for every system for every program or for every circuit. Okay, that's what you will hear as well. So what is in the setup phase? Well, in the setup phase essentially you generate something called a CRS. Um you also hear some so uh CRS um you might also hear something called a SRS structured reference string. they are uh from my knowledge the same thing um essentially a bunch of values that you need and uh what are these values right what are CRS right in this case CRS are pretty simple it's it's essentially well this right so this is a bunch of stuff and uh well look at the commas it's like g1 to the power of alpha g1 to the power beta g1 to power of delta and then g1 to the power to zero to some number. So degree t to negative1 degree t this t is actually the uh I believe it's the um degree of polom if I'm not wrong might be wrong uh but yeah so um and then there's also this value which is g1 to the^ of b * a * * a + a * b j plus c okay so this these are all so the a b and c in This scenario refers to the QAP, A, B and C. Okay. Um and also this this is divided by um gamma. This is divided by data delta sorry. Um and yeah and then this right these are all values that you compute um on top of your groups. So this is computed. So CRS G1 is computed on the um G1 group and CRSS G2 is computed on the G2 group and notice um we compute a lot more from from the G1 group than the G2 group in this specific case. Okay. So there's also a mention of uh the sim simulations trap door which is alpha beta uh gamma delta and and so let's talk a little bit about what these are. These essentially are secrets that you choose during your setup and these secrets we call them the simulation trap door uh but you may know them as toxic waste which means exactly what it means. They are things. These are values that if known uh by well if known by anyone uh in this case if known by any malicious actor you can create a fault proof that's why we call them toxic base. Um so yeah and these values we use to essentially well to a certain extent we we use it to add security in in our protocol itself. Um to put it very simply um these are all values we use here so that um we can make sure that we can use so these values we we we've put them here so we can essentially use them to compute um compute our um result later on or compute our polomials later on without having to reveal um witnesses. our witnesses in this case. Um yeah and these values are only known to the approver or more accurately they are only known when it's first setting up and again as I said because these are these are toxic ways we usually have compute um these values uh using MPC multipet commutation where many everyone contribute a piece of secret and then we combine them into this in that case um as long as one of the parties um dispose of their part of the secret. Um it's relatively it's secure, right? Um of course. Yeah. So there's a sense of trustedness in here. So that's why trust is set up. Okay. Yeah. So here we also call tile a secret evaluation point. Um and Tao essentially allows you to um compute and evaluate any polomial um at a point of t without knowing ting to itself. That's why um we also call this powers of towel here. So we call this entire thing the powers of towel. Um we also use this quite often. Yeah. So yeah that's that's what uh is this is an example. We have this QAP from previous chapters for the tree factorization problem. Um these are this is the QAP and then we essentially have this as our simulation trap door. These are all the secret values. Okay. Um this is an example by the way. So don't we usually would not use this we would not use something that easily memorizable for our similar tractor and usually because in production we'll use a relatively big group in with a big order. um these value are very hard to remember anyways right and and usually we also wouldn't really save it anywhere again um EMPC and all um so yeah so here it's just showing you that um given uh your QAP and let's say after you compute uh your common reference string um and then you can also you comput a common reference string like this, right? And then you can compute actually um yeah there you go. So this is a common reference string for the V63 torsion group um based on G1. So you need your QAP to actually compute this um and yeah G2 similarly you need to compute this and with these two um these are public right. So by publishing this you do not reveal anything about the secret values. You do not reveal anything about your um your witnesses. I mean in this case there's no even witnesses or instances to talk about. This is just the circuit itself. But yeah you don't reveal your secret values that allows anyone to generate a fake proof. And these are things that will allow you to do calculations and do your proving and verification job um later on. Um yeah so uh what I'm talking about is essentially let me just show you so in each phase we okay let's go through this um so set phase requires R1 CS you generate a CRS and sim trap door again this usually are not really used in in production um there's also the prover phase where you given an an RNCS a CRS so here RNCS usually is in the form of QAP at this point but yeah RNCS S CS which is common reference string in andw instance witness recall what instance witness are instance witness are instance is a public value witnesses are the private values private inputs yeah so we generate a proof pi verification phase the verifier will have a verification function that accepts the R1CS the CRS the instance and the proof note no witnesses because verifier cannot know about witnesses they are private um so yeah with the proof and the instances we are public and the CRS of course you need need circuit information to know that what you're computing against um with this you you can basically verify if your proof is correct if this is correct right so you will accept or reject and finally sim uh simulation right simulation um this essentially again this is an algorithm that basically given are the the trap door um or toxic waste the CRS and the instance you can generate a fake proof without knowing the witness In which case in the correct way you only can generate a witness you can only generate a proof if you have a witness right in this case yeah given your secret value this is to show that I can generate a fake proof if I know the toxic waste yeah okay so yeah that's that's essentially uh what it is and in your surface you're generating your CRS and your tra um Yeah, just slowly scroll down. Yeah, here it's showing you that essentially um given you have your CRS, you can actually evaluate polomials, right? Because so here um look at this. Okay, a2 t1, right? A total t this is the point evaluated at to you can see that a to um expanded is this right and uh doing this product with g1 if you expand it is 6 * g1 * g1 + 10 * 0 to 1 g1 + 10 * 0 g1 and 1 g1 and 0 g1 is known why is it known it's known because it's in part of the CRS But by knowing by knowing Tao 1 G1 and TOA0 G1 you cannot get TO1 or TOA 0 um you cannot reverse compute it because of uh because of its um what's it called it's a discrete log issue it's a list rock assumption because of this rock assumption yeah um but here if you look at the CRS definition let me just take a picture of the uh just for you to be able to see it. Give me a moment. Yeah. Okay. Let me just do this.Oop. There you go. So given this, let's go up here. So yeah. So to1 G1 is here, right? You know it from here. tow 0 g1 you also know it from here because it's 0 to 7 degree. So in this case uh because here recall when we are computing it for the um for the factorization problem we are actually computing it everything here. So uh looking at this uh look at here. So this is G alpha, G beta, G delta, GT 0, GT T1 or G to T0, G to one. And then this is uh this right and then this are these again four values and then here in this case four values because to M essentially and here uh which is this right? Okay. And so that's why we can compute um compute this. We can just substitute it in. Um you'll see this a lot um because well we we want to be able to compute something without revealing our toxic waste or without knowing the toxic waste and this is how we do it. Yeah. And we will you'll be able to evaluate this polomial essentially. Same here. Yeah. That's that's what CRS is good for. CS is very very useful. So that uh when we need to evaluate something we want to evaluate polomials it's it's pretty easy to do. Um yeah anyways okay so here here is just showing you how how this will look like in snarkjs. Um, so I'm going to skip. Uh, before I continue, I'm going to get some water. Uh, in which case, any questions so far? Okay, I'll take that as a note. Okay, so let's go to the pro phase. So proof phase, recall proof is essentially it's it's a function that accepts R, CRS, IW, right? uh the the the R1CS the common reference string the instance the witness and so yeah in in this pro phase um you will you essentially start the proof generation right you have some statement you want to prove and here is where you do it and yeah um so yeah I'll go through this a little bit um there's some polinomial h um that is in this form um and you want to do h * t t is your target polomial um divide by delta and then put this as the exponent of a generator. So G1, so this one. Yeah, thank you. It's here. And then you can use your common reference string to compute um part of this. So because you're computing this with on on the point of secret valuation um you can compute this by again substituting right your h0 your your t0 out and this is known and so after this um there's a sampling of um two two random uh elements RT and then we'll essentially compute the curve points again these are known we are computing uh this for witness variables um this is known um because so this entire thing is known uh G1 to this power to G1 to this uh is known because we computed it um in our common reference string and we'll get essentially this right ga GB G time G delta And yeah a lot of this we can get it from the common reference ring AB um these values are from the RNC these values are referring to polinomials in our RNCs. Yeah. So um after this step this few step we start to generate our proof and um to generate our proof um it's in the form of G1 A G1 C G G G G G G G G G G G G G G G G G G G G G2 B this ABC is no longer referring to the um RNCs. This is the portion of the proof. Um so um here essentially how do you generate? So the proof let's say for example this is an example right um you proof um polomial polinomial with instance and and witnesses is this and uh yeah you'll do the calculations get some value and then start generating your points witness and your witness here and then we'll start generating a b and c. So yeah, it shows you how how it's done here. Um, this is an example on the tree factorization problem for the group of orders 13. Um, yeah, but essentially here you'll do the calculation for A, B, and C, which is part of the proof. Um, I'm just going to quickly walk through it. And here, okay, so here what we need is actually G2. We are not using this but we are generating we are calculating this for our C here where you can see yeah we are using uh B um * G1 or B G1 to power B actually um so yeah and with that so with this actually so we need to generate the three portion with a which is generate like this I'm not going to talk like like go through this in terms of a single and single. But it's essentially the the cross productduct of this, this, this, this, and so on, right? Uh W2, W3, W4, and then this, right? Uh, of course, if you have more than four witnesses, it will go longer. It can go longer, right? Um, there's also instances, right? If you have more than one instance, it will go longer. Um, same goes to B. Um, same goes to C. Okay. Um yeah. So with this we can then generate a proof which is consist of A, B and C or in this case um A C and B. Okay. So B is this one because this is actually the result from the from group two. Uh sorry from yeah from group two. This is the result from um group one. That's why you see this right. Recall group two I believe is an extension field. um it's an extend yeah it's an extension group if I'm not wrong uh from previous chapters um that's why you see this V values here um yeah it's torsion group I believe to more accurate I might be inaccurate in this but yeah anyways um so yeah so this we get a proof from this calculation um a lot of it that we want to calculate so let's say for example like we want to evaluate the the the the circuit itself on some points I want to calculate the values We can very easily just use the common reference tree as shown here. Right? So with this tree value, we can now share this proof to any person who wants to verify it and then they can verify it. Okay. Yeah. That's why in uh in um I believe you can see this very clearly if you use circom the proof that generally usually consists of three parts A, B and C. This shows um again um just the how how this looks like in in snarkjs. Okay, that's essentially everything about proof. It's pretty pretty quick um in this case cuz um well uh for those who are interested I would highly recommend try to implement this because they actually do it they explain this in a very compact way in this book. um maybe we should go through it um in another um session or workshop where we actually try to implement this or we go through another book that that goes a little bit deeper into each part of this approval process. Um but yeah, I'm here they they go through it very quickly. They they just talk about the steps like very quickly A, B and C, you know. Um so yeah. Um yeah. Okay. So verification uh verification essentially um recall verification again here let's go back to here verification we take in a few things as an input let me just go here yeah there you go um R CRS I empai the proof instances CRS and RCS or the program so um yeah So uh there's an assumption of course that uh each verifier can can compute the pairing map efficiently and have access to CRS. So yeah your CRS usually is shared. So without the CRS um the verifier is not able to produce or able to verify anything. So that's why you you usually will share your CRS right. Um yeah so this to verify it checks pairings. it just does pairing check and this is efficient it's it's usually very efficient um that's why um people who use CK proof to like when you generate a proof and you can verify everywhere it's very and it's very cheap to verify um you can use it for kind of compression purposes uh when you send messages uh to a certain extent um this also means that to verify the fact it's very easy um so everyone can do it um you don't need to rely on a big fat computer and uh that adds some um trustlessness to things that you integrate this with. Um yeah, anyways um you essentially need to verify this, right? Recall pairing pairing checks. What it does is essentially when you do a pairing check between between two points, it makes sure that yeah, if the pairing check is true or if if this check is true, if this if the left hand side equals the right hand side, you accept the result. If it's not equals, you reject the result. So yeah, that's what it is, right? So this pairing check essentially checks your proof um to see that if it's correct based on so your instance your secret toxic waste uh and your proof right okay so um essentially well you can you can think about it like here right it's doing this check so e a is this e alpha beta is this e i uh gamma is this and then EC gama is this. And if you look here they are all also they they equivalent right so uh 12 108 should be equals to 30 + 16 + 36 I believe. Yeah. So it's a times times is a plus. So 30 + 16 I think. Nope. Wait. Nope, it's not. Uh, let's see. 30 66 70 82 actually. H, that's interesting. Uh, I might have gotten this wrong, but it should be equal actually. Yeah, this should be equivalent and times in this case equals plus. So, yeah, not sure why it's not equal, but anyways. Yeah, this should be equivalent to this times this and and this, right? Yeah, there you go. This goes to four and this is equals to this which is equals to four. Yeah, actually is equal because this this is not in a let's see I think this is after modular 13 arithmetic. Yeah. Or mod. Yep. Your modular 13 arithmetic this and it's the same. Yep. So that's why um since the left side this uh 11 108 mod 13 is four and uh in this case um 82 more 13 is four and both will send them up equal. So this pairing check pass. So you can accept proof. Yep. So verification uh for a pairing based um proof systems usually are just pairing checks. Yeah, that that's it. That's all about verification. Um yeah, it's very compact. Again, um for those that really want to know practically how this works, implementing it is the best choice. I've seen some of you have submitted PR to the repo that I've shared. Um I've gone through some of them. I haven't finished reviewing another ones of them and um yeah thank you for for those who actually submitted PR thank you for submitting feel free to submit after even after this this uh this class um yeah I will continue looking at them after this as well um us and talk about it in a group as well yeah okay finally proof simulation so proof simulation is just to show that with the toxic waste you can actually generate a fault proof and Yeah, essentially show you how it's done. So with this you can generate because you know what alpha beta tama delta and and um tao is you can create a situation where or you can select values where um you can select values in which you do not know the witness to generate something that works for the verifier. So um it's essentially just algebra in this case. I think they show it here. So yeah, we given i= 11 can just choose arbitrary elements a and b and then compute it so that it's this right and and in this case um when you verify this it will be valid because you just essentially need to well as long as you can compute something valid it um in in this case, right? The verifier will verify as correct and you can make it valid because of the secrets that you know from toxic waste in this case and and this is valid because of that you essentially if you know your your secrets you can essentially do this right you can essentially generate something fake and um yeah I mean as seen here right so um let's see let's go through this entire thing let's try to reset everything um So okay forging use simulation in combination QA and two arbitrary F elements from scala F to compute G1 C for instance I1. So yeah because if you know delta we can compute this times this time this this is known actually. Yeah. So the main point is A and B we can select ourselves. Um and this is computable because we can choose A and B, right? Um this this is computable. We can just make it that it's computable without knowing the witnesses. Um recall originally looking at the prover. Let's look at prover. We need to do this, right? We need to compute this. But we well in this case um we don't know um delta or top right and so we we cannot because we don't know that we cannot just choose random stuff because everything here um or like know like later on when we use this calculation if we choose something random here um as values um instead of um doing like an evaluation, right? Um we we might create values that does not pass the verification. But in this case, because we can choose and we can just look at what the result is. Um right, we can use it. We can just choose values that will satisfy the equation and then we can forge a false proof. Yeah. So yeah competition G assumption makes G1* alpha beta from G1 a alpha G1 beta infeasible. And this is very important because of again um right so this essentially if you look at the setup phase we can only do calculation based on like for for these values we don't know alpha beta but if you know alpha beta we can change it up so that um in the pro stage right let's look at this I don't think they have like a full thing here um yeah not this uh is it this but because we if we know that we can just do this calculation and then it's very easy for us to compute G1 and C. Yeah. And this will be valid if you verify this. This will be valid. But it's not actually a false proof, a forge proof. So again, I want one more thing. Um so why is it possible to generate a false false proof in the first place? because um proof system this graph 16 um and I think most proof systems are probabilistic. There is a very high chance as in probabistic as in there there is a high enough chance that your proof if it's correct your proof will be accepted and if it's incorrect your proof will will be rejected. Um there's a high probability that that's that is true. there's a very very very small possibility that you can generate a false proof out of the blue. But if you have the secret values, you can now do that. Um because if you don't have the secret value, it's very hard for you to compute or very hard to for you to compute anything um from the group itself, for the psychic group itself. um there's a high chance you cannot reverse computate uh reverse compute some value um from the group into the value of what the actual value is. Yeah. Uh and that's why it's hard right um and if you want to go through that it's usually more than it will take more longer than um than than the time we have in our universe. of course uh not considering quantum computers um although that's quite some time away but yeah so it's a probabilistic protocol okay so that's something that is quite also quite important so uh I think that's it um for those who are interested please try implementing it make a PR to the GitHub ripple um for those who have more questions You can ask me via PM at p message on telegram or another platform you may know me from. Uh you can also ask in a group so we can all learn together. Um here I think that a lot of you a lot of this is actually unfortunately um very much compacted. So if you are interested in a little bit more detailed explanation um we you can just stay in a group and we can we can try to arrange either a workshop to go through a little bit more detail in in what this is doing. This is a good example actually the examples are pretty okay u but you need some time to actually go through them to understand why why it works right. Um yeah, if you want that yeah to tell me. Um but otherwise if there's no questions then this is the final session. Oh well I guess there's no questions. Thank you very much for coming uh for this eight weeks or so. Um yeah, thank you very much. Um, see you guys next time in another session. Uh, and for those who are interested in uh, looking at the recording, the recording is actually available on if's YouTube channel. Go check it out if you want to go through what's uh, what's there. Um, you can also subscribe if you want to see um, more videos that that we might record in the future. Yeah. Thank you very much. Have a nice rest of the day. Um, bye-bye.