ETHWarsaw Meetup 0x0D (#13) Browary Warszawskie (26.03.2024)

[Music] [Applause] [Music] hey uh GM waro uh welcome to the Meetup number 13 uh here in the new location um so uh we can start getting used to this location uh because uh official announcement we're going to be hosting the next e foro conference and haakan here in bra um so we're going to have the whole place here and we're going to do a great conference in hackaton again um so yeah 5ifth to 8th September and we're also going to have a full warsa blockchain week already discussed uh uh with some partners that we're going to have uh more events uh also around zero knowledge um so so yeah um so today uh we're going to be talking about zero knowledge um so we have got two great speakers uh first we're going to have Leon um who is from V layer Labs it's a freshly founded starup that is building uh on top of um zero knowledge and then we also have got Marchin from matter laabs uh for if someone doesn't know what mapse is is the company behind ZK sync um so so yeah we're going to talk a lot of technical stuff today uh we're going to dive into zero knowledge proofs and then as always we're going to have a little bit of networking pizza and beers um so yeah uh get ready uh and without further Ado Lon please uh come come to this stage and uh let's start hey everyone uh my name is Leo and today we're going to talk about arithmetization but before going in into what is aration and how it's useful let's as a quick reminder talk about Z knowledge in general and how it's in the context of ethereum so and how it's relevant in the context of ethereum okay uh so in order to scale ethereum we decided to offload some computation to the rollups and do them in the rollups and then commit just the results of the computation and there are two main types of the rollups there are optimistic rollups and there are zero knowledge rollups and optimistic rollups the way they work is we do something we commit the results and then we have some time for the people to challenge us so they can submit Pro FR proof that they can be like hey this result is actually Incorrect and here is the proof that this result was incorrect and then the result gets reverted zero knowledge rops they have the opposite approach to that uh before submitting the result that might be incorrect they submit the proof with the result and there are some mathematical arguments that if the proof is correct and verified then the result is also correct so it has some benefits because there is no need for this uh challenge period and the results that are submitted on chain can be immediately useful in the smart contracts so we don't need to wait a week for the withdrawal and they have in general better security warrantees but it comes with costs uh but we're not talking about ZK rollups today we're talking about ZK in general and ZK is like part of mathematics which is useful in the cryptography and in the ethereum space and it allows us to verify the computation so ZK is verifiable computation I think the name is a little bit unfortunate in this context because most of the times we use ZK we actually are not using the zero knowledge capabilities but we're using the verifiable computational capabilities and when I say verifiable computation what I mean is that we can offload the computation to some other party the other party can compute it and then provide us the results and the proof and we do not need to re-evaluate the computation we just need to check some mathematical properties on the proof uh but under the Hoot the mathematics that allow us to do that is very complex but allows us to do very simple things so we cannot just like take any python code or JavaScript code and make it verifiable but we can do just two basic operations there but arithmetization is a technique that allows us to take complex uh abstract programs and compile them in a way to a set of very simple Gates we call them but basically those are addition and multiplication operations and then we can verify this computation so arithmetization to sum up is like a compilation to a back endend that can be verified in ZK and uh there are different languages in ZK and there are different Technologies uh today we're going to be talking about Noir and plon uh plon is a proving protocol so it's something that it's like a mathematical and programmatic constraint uh not constraint but like system that will take our program after compilation and prove it and Noir is a programming language in which we will write our computation that later can be proved uh so without further Ado now we have some context uh why it might be relevant and let's jump in so this is the plan of the uh presentation we're going to talk about the differences of verification versus computation because they're very similar but a little bit different and when we write ZK circuits and ZK circuits are like programs in ZK Al exp l or why we call them circuits we actually they do verification not computation then we're going to talk about the ZK execution environment it is similar to how in ethereum we have evm which defines what we can and cannot do and assembly is our language in ebm and that's all things that are allowed in ethereum uh it's the same in ZK we just have like let's say a ZK execution environment which dictates what we can and cannot do and then we're going to start expressing basic building blocks because it will be non-trivial that any program can be written in this style in this very limited Z KVM but we're GNA start from the bottom we're gonna start from building some basic blocks and then we're going to build on top of them and then we're gonna start combining them and then we're going to show that it is actually touring complete and you can actually do whatever you want almost whatever you want because it's limited in size but we'll see the limitations later uh then we're going to talk about uh the real Technologies so initially it's going to be about the theory behind that but then we're going to talk about how it's actually implemented in the tooling so we're going to talk about about the plon gate format and then as a bonus material I'll show you some results from an actual compiler to show that what we came up with is not just an idea but it's how those systems actually function under the hood uh disclaimer sometimes for pedagogical reasons uh there will be some partial truth here just so it can be explained but if you feel that something is no yes please raise some questions so computation versus verification uh when we Rite in normal computer programs we do computation so we want to get some results we want to compute something and get the result and this result is what we're seeking but when we do ZK getting the result is not the interesting part the interesting part is to prove to someone that this result is correct that there are some properties about this result that we satisfied for example when we use it to verify transactions on the rollups okay for example when we use it to verify transactions on the rollups uh we actually do not need to just compute the new state route of this transaction or the new storage values but we need to verify that we did this computation correctly and that there was no fraud in the meantime uh so it is a little bit of a paradigm shift when you write those programs because we're not we're doing a verification not a computation and our result is usually Boolean success or failure did it verify did it not verify uh but verific uh computation is always part of the verification because in order to verify something you first need to compute it uh but this has some important implications on how we write programs because some parts are much easier to verify than to compute so for example uh as in cryptography we have some functions that are one way functions it's much easier to verify the hash uh the reverse of the hash than to compute the rever of the hash so like that's impossible uh in Practical terms but some of the things are much easier to verify and we will show that in our code uh it sometimes will be useful to compute something uh not inside of the circuit and then just verify it inside of the circuit uh ZK VM it's not a VM actually but this is how I call it for understanding so this is what is allowed at our backend so this is what we can do this is what we're operating now so we have just two operations uh addition and multiplication addition is free and multiplication costs one so it's similar to how we have gas and solidity and different op codes uh have different costs here we have two op codes additional multiplication and uh the values that those OP codes operate on are all field elements and when I say field I mean 255 bit numbers modul a prime so we use modular arithmetic here and very big numbers which are similar to the words in evm uh but they're 256 bits so this is a little bit smaller uh but it's not very relevant at this point and our output is Boolean true or false so we can at the end uh compare some things together and check if they're uh the same or no and this is the output of our computation and this seems extremely limited and you think hey how can I like Express anything remotely useful using that but this is what this presentation is about so I will show you how to express the basic programming Concepts and then by combining these Concepts you can actually build a programming language and in that programming language you can build useful software uh so yeah uh those operations are very simple but the power comes from combining them you can take the result of one of them and you can plug it into another operation so here you see at the first line we did addition of two input variables and then we took the output variable and did a multiplication and this is our expected result and at the end we do the verification so the last step can always be presented in in a form of comparing something to zero and our verification is essentially finding a satisfiable solution and the solution should satisfy all of our constraints and compute to zero at the end and we do that by just uh assigning last step minus value we expected to be equals that n and that n should be zero at the end um and important part as I said we can do the computation for free and only pay for verification this is called unconstraint and there is a keyword in Noir unconstraint which allows us to write some code which we not pay for executing but then we get results from this code and those results are untrusted and we need to verify them and we need to put some constraints on them but sometimes it's much easier to verify the results than to compute them in the constraint code uh so here is a scheme of what's going on so on the left we have a program which is not a very useful program but it computes something it's a program and it's in some soda code and then this presentation is how we convert this program to a set of gates I will talk about Gates now and this set of gates can be verified and uh this set of gates to some people would reminded the circuits and that's why it's called a circuit so it's like a circuit representation but gate basically is just a a building block so how we told that we have two operations additional multiplication each operation has two operants and it has one output so Gates have wires how we call them how they connect to other Gates and this gate we see has a left wire the right wire and output wire so each operation has the left operant right operant and the output of the operation and then we connect them together in the graph now we see that it's a tree but it's actually direct a cyclic graph uh because we can uh it can be more than a tree but we will see that on the next slide and we will explain how we uh convert this program to this representation because this representation can be proven and can be verified uh let's start uh this uh representation is also called polinomial representation for the program and uh uh it's called polinomial because if you just take some variables and do additions and multiplications in them it's obvious that what you get is just a polinomial over those variables uh if you simplified just additions and multiplications of those variables and each program can be represented in a polinomial form uh but some programs just have very very extensive and long polinomial forms and sometimes it's very inefficient but we will show that it's possible and because our backend let's say is a polinomial we will start with uh representing the computations that are uh the easiest to represent and this is Computing the polinomial so uh in the case some things are much easier than other programming environments but some things are much harder so like in the normal processors the easiest you can do is like or some bits or exor some bits because this is the basic building block of a processor the gates and then not here the building blocks are polinomial so the simplest you can do is fi addition and field multiplication but then you need to express other things with that and if you start to express like xsource that actually becomes pretty complex but we will not show how to do it now but I think you will have the idea after this presentation so let's start with expressing the polinomial let's say that our task that we're trying to prove to someone is that we know a root of this first polinomial uh so um that we know some X1 that uh when added to X2 uh for example let's say this X2 is a constant and squared then it gets zero this is not very interesting but it shows us how we can combine the gates and it shows us uh how we can compute some things in different ways so here we can just have one addition and one multiplication Gates on those two input variables uh and we can see that multiplication gate can have left wire and the right wire connected to the same gate uh and this is a polinomial representation of this program but we can also present it in a different way uh for those familiar with the uh binomial representation this is the same as this one and then it will look a little bit different uh because uh yeah this gate has Mouse yes this gate has this left wire and this right wire this gate has this and that at each gate we have written what it actually represents what it actually computes and then there should be a two here but you can actually multiply things by a constant when combining left and right wires and then you can compute it with a bigger amount of gates their computation result will be the same but it's just showing that it's not a unique representation and here we have a generalized representation for computing that something is a root of this polinomial so you have constants you have input variables and you first do additions to uh get those intermediate one omals or how would they called uh parts of the polinomial uh and then you multiply them together and you aggregate the results into a single single impression expression uh so this was the example of some arithmetization and what we can we can analyze it and uh uh talk about some of the properties using those examples first things to notice uh not to notice it cannot be noticed here but first things to talk about is the depth doesn't matter so it's not like we compute from top to the bottom uh and it's not like this one will be more expensive than this one because this one has a depth of four and this one has a depth of three no what actually matters is just the number of gates for us uh so yeah uh so this one will actually be like slightly faster because it has just two gates and this one was slightly slower because it has five gates and this one has the how many uh 2 N minus one Gates um second property is this tag is a cyclic as tags are deag is direct I cyclic graph and uh it is a cyclic because we cannot take the result of something that is yet to be computed and use it in the computation uh it's quite a natural property and but from that we can express the property that we can't have arbitrary length Loops so one of the basic B things you want to have in programming is after you have an if you want to have a loop but here it's kind of impossible and that dictates a lot about how we write programs because you can have a loop of length like three four a s whatever but you can't have a loop of length n because those Gates does not allow you to express uh such a uh such a loop but there are techniques to overcome that uh which are out side of the format for this presentation but if someone is interested I can show you later and it can be really large but it should be bound in size so here if we compute this polinomial for I don't know 100 uh elements it will be a lot of gates but we know the size of the circuit from the top and it should always be like that so in the Practical problem programs that we write we have millions and millions of gates but we always know it's not the number of gates is not dependent on the inputs it's the same for all the inputs so you do the same computation independent of which inputs do you get so for example when you think about verifying the transaction you verify that transaction has such fields and then you verify the transaction signature and independent of which transaction you verify this is always the same amount of compute and if you have some optional Fields into transaction you add the verification there but then you disable it uh so you still have those Gates and you still pay for those Gates but it might be not understandable now we'll talk about it later how to disable stuff and uh yeah one non obvious fact is that any computation can be presented in this form but it may be inefficient and we will prove this fact now with given examples actually I'm not tracking time how I on time okay uh so let's start expressing basic operations and one of the basic operations that will show us a lot is the division uh but we're operating on fields we're using modular arithmetics so we don't have like division in normal mathematical sense but we have division in the discrete math sense so we have modular inverse so a is a modular inverse of B it means that when you multiply a by B you get one so like in normal Division if I take three and then I divide by three so like inverse of 3 is 1/3 that means that 3 * 1/3 equals 1 and one is a new neutral element so we're operating model of B which is this Prime and we are trying to check if a that someone gave us gave us is a modular inverse of B and oh it's not that someone gives us it's that we know this inverse and we can just compute this a in unconstrained code because uh if someone remembers from discrete math Computing modular inverse requires you to uh do some powering uh from little foras theorem and it's quite expensive even if you do binp power but we can not pay for it and get this a for free from unconstrained code and then just do one multiplication and one check to verify that it is in fact a modular inverse so that shows one important trick in ZK that sometimes it's much easier to verify stuff than to compute it from the very beginning so we can do uh computation and unconstrained code so this is actually like not a basic operation we just do multiplication here to check but it shows the trick that we will use in other operations uh second operation that we are trying to express is that X is a root of this polinomial and as you see this polinomial has two Roots it has zero and one so we can have two correct solutions to that uh this I know understand this might be not very interesting but uh it will show us how to uh compute other things later and if you want to show that X is the root of this polinomial uh here is how we can express it with those Gates so for this polinomial we first compute x - one assigned to X1 then we multiply it by X and then we check that our result is equals to zero and we know that if this result is equals to zero then the X was the root of this polinomial and here is the same operation with uh the actual values for uh xal 1 so first we compute this part it equals to zero and then we multiply and then we get 0 Z and if you substitute something that is not the root of this polinomial like two then you'll have 2 - 1 1 here 1 * 1 1 and then it will not equal to zero um and then uh what if we want to check that X is a bit is a binary bit uh we see that's actually the same operation as we just derived because binary bit can have two values it's either Z or one so if we check that X is a root of this polinomial it means that its value is either Z or one but it cannot be any other value so that's the same check to check that X is a bit so if we have an input value which can be fielded which can be quite large we can easily constrain it to be a bit uh using just those two operations uh so now what we want to check that X is a ternary bit and a terminer bit is a bit that can have values of 0o one or two well that is a very similar task to what we did before but it shows how polom computations are useful for checking set inclusion so we can just take this polinomial and this polinomial has zeros at 0o one or two so if x is a root of this polinomial that means that X is a ternary bit so now let's say we have inputs B 0 and B1 and we want to check that it's a correct bit representation of X where X is less than four so using our building blocks that we just derived we can check that b0 is a bit B2 B1 is a bit and then we can combine them together using additions and multiplications and check that we actually get x uh here is this written in soda code uh so yeah we use the operation that we just derived and then we do a linear combination of those uh substract the value and check that the result is equal zero uh so now we can check the equations if we have uh the bit representation for the value uh and if the value is constrained to be under some power of two uh this is our range check and range check is one of the basic operations in ZK uh because uh when you look at the code that compiler actually produces under the hood it has a lot of wrench checks uh because the numbers that you get uh the field numbers are not very useful because you cannot do a lot of operations on them but then if you actually have normal numbers there like u64 u32 they are constrained and they have rench checks on them and that's why this operation is relevant because it allows us to have some building blocks that are much more useful than the field elements uh and when we start programming sometimes it's okay to have like operations that linear compute some value but it starts getting interested as soon as you have an if and as soon as you have uh some branching and you need to do something if this happens or something else if that happens but uh it's quite non-trivial how to have an if using just arithmetic Gates because you just have additional multiplication and this is an example of how we can have an if so we can constraint p uh p is like predicate it's uh uh the condition of this if we can constrain it to be a bit we can compute this predicate and then we can compute this linear combination of P multipli by Den Value Plus 1us P multili by L value and and this has some interesting outcomes so first you see if p is one then this expression evaluates to den value because in the second part you just get zero multiplied by L's value so it doesn't matter what is the lse value but if p is zero then the second one is turned on and the first one is turned off uh so it works like an if on in terms of values but it's not lazy so for the normal if you expect if the condition is true then you execute the then Branch but you don't execute the El Branch here you execute both branches and that's the only way it can be expressed that we know of uh and it has some interesting outcomes for example if in the Dan Branch you check oh if I'm inside of the table if I'm still inside of the array then do something on the array otherwise it's like out of bounds and do something else but the problem is that you think that you do something in the den and that your predicate is true because you're in the den but it's not correct because then is executed even if the predicate is false so you can still have array out of bounds and you need to program around it so that your ifs can execute both van and else Clauses without causing any exception and outof bound errors and it also obviously has performance implications so if you start Computing um I don't know Fibonacci numbers and you compute them with the ifs like that then it's going to be nonlinear but it's going to be Fibonacci real Loops um so there are two uh essential types of Loops in programming constant length and variable length constant length is when you know that you want to do something like four times and in Noir and in ZK for constant length Loops just linearize uh linearizing the loop it's just taking the loop body and copying it end times so so if you execute something four times loopop is just a syntactic sugar for saying copy this block of code four times uh but if you have a variable length loop it's essentially a loop and an if at the end and because the ifs are um not lazy you can't have that so in the languages that we have available for us now variable L Loops are not possible uh and sometimes you can almost overcome it with an if inside the loop uh but then you still need to have an upper Bound for the number of iterations of the loop so you can have like uh iterate over the maximum length of the array but then if you're out of bounds then just don't do operations mean do operations but multiply their results by zero um same technique as we used in an fp4 so now let's go to the normal operations that we have for free in the normal programming languages but that require a lot of introductions in ZK let's say we want to compute to check if a is less than b um this is it and we'll use uh uh our bit splits that we developed before this is obviously P code uh but in order to do that we have we need to have range checks and we need to uh know the expected ranges for A and B but let's say we know that A and B are four byte numbers so like u32 and then we will split them into bits and have those two arrays of bits a beats and two bits and then we will uh use the same technique as we used with B1 and b0 here uh to check that our bit split is correct because uh this first operation is done in UNC constrain code so we cannot uh be sure that it's done correctly we cannot trust it we need to verify it in constraint code but after we verify it uh we know that it's a correct bit representation and then we can rely on it and then we can do our comparison if you look at the numberb is bits by bits then you see that if the first number is less than the second number then there is a bit where uh on the left it's less than the second bit but all the bits left from it are equal so that's what we do here it's essentially like a linearized loop where we go bit by bit and we check that one bit is less than another bit um you can notice that we haven't uh developed a tooling to check if one bit is less than another bit but it's actually very simple because you need in bits if one is less than the other then it means that the first bit is zero and the other bit is one so you can just assert that and yeah so you will have 32 ifs here obviously it's done by programming language under the hood we don't do it like that uh but this is what happens under the hood so if you do this and you get uh 32 multiplied by three constraints don't be surprised because this is the only way to do that and [Music] right wire there is the constant here and the value that comes from the right wire here is the value that comes from the output wire this is this index always four and this is the multiplication part so it's we don't have addition or multiplication gates in plun we have one gate which can do addition and multiplication and it can also add a constant so the whole program is a set of gates like above and can prove two things we can prove that all constants all constraints are evaluated to zero and that the copies on the wires are done correctly because even if all constraints are done correctly you also need to check that it actually substituted the correct values from the previous computation to this computation and when we look at our basic operations so like addition in PL gate will be one on this parameter one on this parameter and uh zero on other parameters one one on the output and addition of constant will be one on the left wire and one on the up output and this constant here and multiplication similar but we just enabled the multiplication part of this gate and in general at the beginning I told you that uh addition is free and multiplication costs one which is not fully correct uh but it's usually kind of correct in Practical programs because uh additions usually combine together with multiplications in those Gates and uh because of that uh the number of multiplications is a good estimate of how how many gates will we have and now we'll see some real life examples of some real life computations uh in the compiler those will be pretty similar but we'll show you how it works with the actual Gates so first we'll have a program that uh checks if something is a Pythagorean triplet so Pythagorean triplet is that the sum of the squares are equal to the square of the third and yeah so this is the program how it looks in Noir we see that it looks like a normal program uh so it has three arguments X Y and Z and it has an assertion with some arithmetic on those arguments and we can check that uh it's equal under the hood it gets split into multiple Gates and here we see the result of the compilation which shows that the gate size is nine but actually Noir adds five gates uh for doing Noir stuff so the only interesting gates are for that it generates and you can see what happens here here um so this is the witness we haven't talked about the witness but the witness is a tra a trace of the computation so before when we had this linear simple Gates uh the witness was the result the value of the output wire after each step and uh this references the witness so for the Pythagorean triplet initially at the witness we have our values three four and five and then we have partial results of the computation 9 16 and 25 which is squared okay yeah we're getting to the and and then you see that the first gate computes squared of the first parameter and assigns it to the third parameter to this nine the second squares the four ass signs to 16 the third squares the five ass signs to 25 and then they all sum together and the equation is checked and here is how the if is computed we will not go into all of that but uh you can see um that at the end uh if you look at the trace uh and if you follow this later uh we don't have time to go through the ni but it's essentially the same as we talked before so it first computes the predicate and then computes the then and then computes the else and then takes a linear combination of this P multiplied by then plus 1us P multiplied by lse and it can be seen in the results of the actual compiler uh thank you for listening if you have any questions feel free to ask them or we can talk after I can give much more details and if you're interested in doing stuff like that we're hiring y questions so it's a simple question just you know couldn't see so fast um how much possible it is to do optimization of a program because I see that you you know you can do one with many IFS then maybe you can flit it out and can you automate it is it already something is being automated and stuff like that uh so I think there are two places where you can do optimization you can do it on the compiler level and you can do it uh in user space let's say on the compiler level one of the main optimization techniques is doing lookup tables as they're called and so here um some computations are very complex but they're Limited in their domain and their co-domain so you can express them as lookup tables being like this is the correct result for this value and this is how for example hash functions are implemented because hash functions require a lot of xors and ores and do are complex but with the lookup table you can just make some computations easier so this is one optimization technique but the other optimization technique that we can do uh it's quite hard to do optimization now in no because you don't have actual profiling uh yet we're working on it and we're like figuring out how to do optimizations but like in programming you can just sometimes uh not like an actual programming but here one of the optimization techniques is sometimes to verify something instead of computing something so switch the computation to unconstrained code and if you can later verify it with 100% correctness then it's one of the optimization techniques so for example if you have rlp in the ethereum sometimes it's much easier to not like encode data into rlp but to decode just some parts of the data that you're interested in any other questions no so thank you very much l uh was great to listen from you um so next up is Marin uh a protocol architect at ZK sync um yeah Le took took that one so one of the reasons we we invited uh Martin here he's a a brain behind this nice book that was distributed at e Denver it's zero knowledge proofs explain like I'm five so uh yeah it did a really great job to educate people uh especially non technical just wait for this oh will okay so much perfect perfect does work actually okay cool going be so much better so uh thanks for the for the introduction it's nice to see all you all folks here when wuk invited me a couple weeks back he said margin come and talk about ZK the whole room of people I was like should I I mean I'm not sure said come on there are humans you should explain it to them in normal terms so here I am talking about why ZK is that ZK is the end game might have heard about ZK everywhere but but why what's under the hood when you talk to people about what is ZK you hear a lot of quotes It's Magic they're magic tricks you know don't look inside and as you know advanced technology is is is indistinguishable from Magic I made a mistake and I looked inside so it's a question for you folks it's your last chance leave this room and think about ZK as this magic thing or stay for the remaining 20 minutes on whatever Pizza arrives to to take a little bit tour into Z and understand some of the intuitions behind us we'll not go that deep as Neo did no we'll try to stay a little bit on the higher level there will be map by the way for people who want want to see MTH there will be a little bit of math but my goal behind this talk is really to talk about the intuition that after this talk you can continue the conversation about the ZK for let's say two more sentences rather than saying it's magic so as I said we'll be talking about the intuition we'll be talking about places how we're using it right now for l2s and what it can offer beyond that and last but not least we're going to look how it works of course not fully because we already have 20 minutes here but I hope that you leave these rooms with actual passion to look more and understand have more questions of diving deeper into so no no one left okay and let's take it away if you were to remember just one slide from this presentation should be this one the important thing about ZK intuition is that I have a proof that I know such a private input that make this function this public input run and not assert so similar to what Leo was talking about this is about verification imagine a function even written normal python has just a lot of asserts two inputs public and private and just lot of and what I'm saying is I'm giving you a proof that for this public input this function doesn't that's it that's all of the ZK now if you think about it for a second so and for conrete concrete examples you know let's say I know the pre-image I know such private input that for this public input this function doesn't serve so what does it mean it means that I know a preimage of this hash how can I prove that oh very easy I'm just going to give you the data right I'll be like hey here's the data you run it yourself but this can be large and after this you know the data too in some cases it's useful in some cases not so much or I can give you the ZK proof a way to to prove that I actually know the private private input but without revealing it it will be small and verification will not give you additional information so to function public data and pro now how do we apply this blockchain this is basically simplified L2 roller these seven lines of code eight right seven okay what happens imagine the public input is a previous hash and the next hash basically a previous block and next block sorry public private input is the state and the list of transactions and what do I do I check that the state is actually the previous state I take each transaction I execute it and then I check that the state is New so right that's what blockchains actually do and a proof of this execution if we can wrap it into ZK guarantees that it really happened and if we send it to L1 and have L1 verify it t down to recap this means I know such a set of valid transactions because this imagine this apply evm is doing all the asserts all the signature checks everything so I know such a state and such a list of transactions that move from previous hash to new hash that is this state transition is correct the cool thing I don't even have to tell you what these transactions are so what can we do the same way how you can think about hashing that enables blockchain previous hash including in the next block the same way ZK can fold computation the cool thing about this is verifying zero knowledge proof is executing some code and guess what you can prove it too so you can basically take the code that verifies some zero knowledge proof proves this execution and take this proof or a bunch of these proofs actually because the interesting thing is not this the interesting thing is this you can take a bunch of independent computation computations compute to create the Zer proofs for them in here verify all these proofs remember ver verifying the proof is just the computation guess what you can create a proof of that they can keep going so the same way how one hash let's say the current ethereum head of blockchain head of blockchain hash is describing all the transactions all the state that happen on ethereum the same way one zero knowledge proof can prove hundreds thousands millions of computations that Happ okay Fant oops okay so to recap why this is the end game so as I mentioned it can verify many compet in one go you don't have to rerun them H in many case you can just get a proof from someone else even someone you don't trust and actually verified yourself means you're saving yourself a lot of compute and lot of latency because these proofs are tiny remember if you didn't want to do the proofs you could get all the transactions from there and run yourself and that's exactly what optimistic are do the other interesting side effect that we're not actively using it but this might come in the future is you don't have to share the public inut private input you don't have to tell which transactions actually contributed or what state actually contributed to this thing so others know that the state transition was correct but they don't know what caused it it's enables all the interesting kinds of private validium by the way and the other thing is yes because you're not sharing all these private inputs you can also save a lot of storage and a lot of network and last but not least and this is something that you be seeing over the next months and quarters is this push towards synchronizing things across the chain basically you can synchronize the state of a different chain with single proof let me repeat that you might be running some chain on the side and then with a single proof I can verify that all the operations you are doing on your chain for the last couple months are correct and after this I can take multiple of these chains and then I create a proof for that therefore aggregating them into one and sharing them with with other thank you that's what I was looking for thank you so at the end of the day that's why ZK the same to to recap the same way how how hashing is summarizing all of the blockchain history ZK can summarize all the execution okay fantastic great sales but where where the catch so if we imagine this is the compute this something what Leo was mentioning earlier this is the comput this is the ZK proof so basically proving is very expensive it requires a lot of complex tricks that compiler outer are really trying their best to hide from you folks that you don't have to think about like oops Loops are have to be static size and they have to fit into all these things so where we are is that roughly one second of compute can lead to hours of proving but this is hours couple years back this was days if not months so we're going orders of magnitude if we keep going probably in couple years this will going down to seconds and this is a place where lots of ongoing research are going okay fantastic so I hope all of you are convinced now that holy moly this ZK is fantastic we should be using all over this but Mar you said you're going to show us how it works okay 10 minutes piz is still not here damn it okay let's see how far we go t down so we take computation we change it to pooms and then we prove it easy right no more okay okay that's why we did the basics if you did not see the book if you did not see the book by the way Distributing it at if Denver and we'll probably be also giving it at e4o if we're able to get it printed on time you can go to this link eli5 Z sing. here you can find a bunch of basically the PDF of the book plus a bunch of riddles I think you should be able to do all of them if not not mentioned and then you will see how we're trying to explain Gates using child-friendly images through all the holes that's why in one move you're proving that all the 100 holes are in the right spot remember if even one of these holes was not in the right spot this would not go through so the similar concept I know this is nend dimensional thinking bear with me I know it's late similar concept happens in pols yeah this is the scary SL like [Music] o let's work through it in like five simple quick steps by the way this is like seventh grade so if you have trouble with this you know just raise a hand I'll explain if we have a polinomial it's equal to zero in some point a it's actually divisible by xus a remember this when you were like okay draw like x - 3 * x - 5 or is the polinomial that has like zero points in five and and seven etc etc right if we make it more General if you have a polinomial that's zero in many places surprise it can act it's actually consist it's divisible by many other by many other polom like this form and here's where slowly magic comes in if these points are special coming back to us folding the origami in a special way if they are the things called roots of unity if you don't know what is this perfect there is some Wikipedia Googling for for this for you after this then this is magically combining into nice this is magically folding to this nice thing so we only have to prove this so basically you can check that this polinomial has zeros in all these places by checking a simple division how do you check it oh easy you compute you pick a random Point s and you check if these things are correct so if you think about it for a second we took one polom okay two fa sorry we evaluated this in one point and if this matches this means that all these points were matching which means that all these all these holes were in the right place okay fantastic uh so we check the value in 10,000 points yay why do we even do that well that's where the Quicky thing so if you do the arithmetization that Leo described and you put your asserts in the right places and then you do this magic folding and you pick the right Point s it has to be secret by the way that's why you have a trusted setup and that's why we use elliptic curves and then you verify it's there okay okay too deep that happens so more more seriously because you know as I mentioned here we have only 20 minute 20 minute 30 minute talk remember the important thing about zero knowledge proofs are these three pieces public input plus plus plus proof plus function and as a user and most of you I hope will be able zero will be using zero knowledge in one way of the other one super important thing is verify the function that's what many people forget that proof is only as good as the function because it's actually the proof of dysfunction execution check your circuits I'm looking at you L2 be check the circuits make sure that the people who are using zero knowledge that you're depending on are actually verifying and auditing the circuit because if the bug is there the whole thing is work and that's if some of you were hoping for even deeper ZK sorry that will be in the next session next time I'm invited here for now I assume that everybody will be able to read the book everybody will at least understand the basics of pols least look up the rules of unities this is fantastic what we're talking about here is the beginnings of kzg by the way so if the kzg was like this unknown thing in the background you just cover 20% of it in 20 minutes so the rest is left to you as the exercise for The Listener so thank you folks thank you very much Martin you're always welcomed and invited here for our eforce apps and conferences uh do we have any questions to Marchin about the presentation or about anything else uh we've had two questions here first so uh in terms of a real life example what's the public input when you're approving uh blocks and what's the private one fantastic so okay so the public input in reality consists of around six or seven pieces it is the the previous the previous hash the next hash we're also usually providing some information about the system for example what is the pub data attached that is like maybe some some blobs commitments what are the versions of a programs let's say in case of ZK what are the versions of the programs running we call this bootload we call the system fun so the way to tldr it will be like previous hash next hash and some hashes related to the operating system or like details that we run because our evm is a little bit different than the pure evm we we do have a separate compiler what not because of the Zs and private is all of the state base is all of the transactions all of the like private inputs counts in Gig GT many gab because for each one one example is when I said the state you kind of need the Merle path for every you touch right you need the Merle path and you need to verify the Merle paths Etc thanks so much at the folding analogy is this like on a high level or are you guys with buum actually using folding schemes nowadays we are using folding and Fry but this has nothing to do with the folding we're talking here right so just just to be absolutely clear this folding analogy was only for the polinomial to show you the idea of how polinomial can verify so many things in one go a complete separate things to this you might hear about things like folding and Fry and recursive circus what not these are separate Concepts to be read and explored by you uh Hey for the recur recursive proofs uh you mentioned that it's possible to proove another proof so do you need to have uh private input from those previous proofs uh or not no because in order to verify the proof should show in order to verify the proof you need a function that was used a public input and a proof right you do not need private input to verify the proof I kind of proof is replacing that right if you had a private input you didn't need the proof you could just like run the function so you mentioned that you using fry and kcg that means you're mixing fry which was originally developed by Stark team and uh kcg which is usually associated with plunk is that the case yes and the real reason is that because yes there are two actually if you read the book The 5-year-old book we're actually talking about fry and and kcg the real reason is that for normal computation we do use fry over the 64bit field over the Goldilocks field but verifying the fry is more expensive because you have to verify all the cues whatnot and ethereum gas is expensive so what we're doing in the final step we're actually taking the fry verification create a kcg proof out of that and we take this kcg proof and that's what we send to ethereum therefore we're saving costs we're saving gas on I also have a question how do I prove I am me like how do I do kyc with ZK like because like we are talking about like high level stuff or lowlevel depending on how to look at it but in practice for normal people what will this uh allow and how how do I for example do a kyc a simple kyc oh wow okay I do not have a slide for that if the tldr answer if you could represent your kyc as a python function with a bunch of asserts you're good and here's what I mean usually kyc comes back the fact that you have something that's signed by The Trusted party meaning have a passport you have ID you have something and the cool thing about zero knowledge and these python codes is you can say the private input will be the something will be the Json file signed by my government having all the data and what I do inside this python function I check that the private input is properly signed and I do a bunch of asserts that the public input that was provided is correct example would be this Json file contain you know 50 things about you from the day were B born to whatever your Mar like all the data you can think government has the public input is just let's say your name and your age and what we do in this python function we verify the signature that the the private input was properly signed by the government and then we just check assert public input name equals private input name assert AG equals a done and the cool thing is that you can run this computation locally on your machine and then you provide just the proofs to others so exchange or someone gives you the python function you run it local you generate the proof you give it back and they can verify normally I would show it better on the on the slides but here I have to do with the hand thank you Martin for your presentation you really tried to explain thank you tried okay and failed I don't know Alexander quco inch Association my question is um you know uh the K proof of for for kyc and the K proof for consensus it is the same thek technology you know in the direct or not or maybe it's different conceptu the same as as I was showing on the slide it's still the concept of you know really the way to think about it for most people is keep thinking python function doesn't return anything a bunch of asserts private input public but of course you know when these python functions are huge like the whole evm computation verification whatnot you will do a bunch of optimizations like fries like folding like splitting it into pieces etc etc versus this is like you know just four lines of python you would just swoop into the kcg or even graph 16 done right so conceptually the same but you know kind of under the hood you would do a bunch of optimization okay thank you thanks uh I have a question U do we have a knowledge or any research about soundness degradation where you do the recur proes in what sense once again what what what would be your example uh like no we take some program and we do let's say recursive proofs maybe on some simple example say Fibonacci and is there like any soundness degradation there when we do recurs so for example at the end we have a lower security bits less of the security bits maybe so this is the part where we kind of getting into the cryptography like deeps of cryptography everything that we were talking about here and when you actually go deep into this you'll see that the levels of security kind of depends also on the on the Prime on the field that you pick at the beginning it's around 250 bits but very quickly drops to like 100 something I forgot the exact values my gut feeling is that yeah we probably lose a little bit but at the same time the amount of folding we're doing even if it's you know 10 20 30 bits it still leaves us a lot more remaining but for this you have to ask the cryptographers that's that a bit outside of my of my knowledge I see I see so my question was only is if we have any like known quantifications of that how much is this degradation you would have to talk to someone far smarter than me thank you okay thanks thank you any other questions yeah sure you are so sure about ZK is the end of the game I mean how is it possible if it is mainly depend on as a user of I mean ZK it mainly gas Fe mainly depends on ethereum gas fees I mean and it really hurts us as as you know it might be the end of the game I mean optimistic rollup is not end of the game and this and and last one which date is the snapshat of zkc thank you okay coming back to your first to your first question uh it's because of this tree folding that I was showing this allows you to take a single proof over hundreds of batches therefore you pay on ethereum once you pay once for a verification but there could be hundreds of batches that you actually bu this where the scale is so even if the verification costs you around $100 right now if it spans over you know 10,000 batches this is just a fraction of a cent per batch which means it's even less for each transaction uh okay we're going to have one last question okay so uh I think one of the issues with uh ZK is that basically the private input can be correct but can be one of the correct inputs right and for example you you brought up the the bridges between chains and this is where the problem is right like you can verify that uh you know the computation given this set of transactions was done correct like this the state transition function was executed correct but it might be just a subset of transactions that were like you know the consensus agreed on or were just like random sign transactions right and can you expand on this problem yes so actually I should I should have not close the slides this was a mistake on my side did it die okay no no no this goes to the recording so okay wow I think it wasn't working for a while oh it is working it was just switched off okay so and and this is actually a very good point and as I'm answering this for people who are not following attention you know the five old can you figure out how much candy mom left the idea is like you got two and all the animals are happy so how much candy mom left and this actually a very good point um and in order to to make now I see everybody's count okay I'm going to give you a hint no three or four and you don't know how much retention of the whole room okay or four the beauty of it and this is exactly what what he was talking about is that you don't know you got your first share of candy you don't know how much left and the whole point was in the in the basic thing I was describing with just public input being transitioned from previous state to next state you hypothetically don't know which transactions contributed to unless two things either you explicitly add this for example a a rolling hash of all the transactions or a miracle tree of transaction hashes to a public input or if it's represented somewhere in the state then you can actually prove which concrete transactions were included in the state and participated in this transtion everybody know that this is three and four yay n okay I assume you did we trust that you say correctly should not trust you should verify please sorry don't trust cool thank you very much again Martin it was very entertaining and very compelling presentation uh big round of applause for you um yeah um so pizza's here uh so it's going to be served with the drinks at the Foya at the entrance so if you guys want to move out over there we're going to have a some time for networking um and yeah hope you enjoyed the the me app today thanks so [Music] [Applause]