From Heterogenous Zero-Knowledge to Layer-2 Performance - Bogdan Ursu

Transcript

[Music] thank you so much for the introduction uh so let's get started okay um this is a very complicated name for saying let's combine zero knowledge proofs in order to get the maximal advantages uh of each system and I'm going to start a bit um more accessible uh just with the concept of a cryptographic proof um we're not going to dwell too much on it but basically we have a approver we have a statement we have a witness and we want to make a proof what does that mean um this proof then gets fed into a verifier and the verifier also needs access to the statement and it's going to accept or

reject and in order for all of this to happen we will also need some seta parameters and to give you a flavor what kind of statements and what kind of witnesses we can we can uh we can support um the verifier for example this is um an example of strong Authentication you can imagine a server that has a big database of a lot of um um encrypted passwords and IDs like National IDs U and maybe some other private information when you want to authenticate the server send you a cipher text the statement is going to be me the client I know a witness such that this Cipher text is the encryption of the witness and then the witness is going to be in this case like my password my birth date national ID so

something really strong stronger than just uh encrypting with a password and then we send this proof and the uh server decides whether um he is going to authenticate or not and the interesting thing is that well we want that the proof doesn't leak all this private data and another example ofic proof which is actually going to be more relevant for this case and it's a case in which we will not need secrecy is outsourcing computation so here the verifier is a weak machine it sends some data some program to the prover the client a powerful machine and the approver is running the program on the input data obtain some results the statement is going to be that our evaluation is correct that we indeed

evaluated the correct program on the correct data uh so that's the witness now the witness is public there's no secrecy sends the proof to the uh to the verifier and the result and then the verifier now can check and can make sure that the prover has indeed performed the service that it was contracted to do so that's it for the introduction for on what can we prove uh but in general the we can prove very complex languages but not extremely complex languages still expressive enough and we're talking here about Layer Two and we're interested in modeling the state transition of the ethereum evm machine so if we want to go from from State one to state two we can imagine this as a

transition function and what happens on their two Zer knowledge rollups is that this transition function is being arith matized and then we comput to prove that this arithmetization was correct and now the the go the the gain that we get is that all not all the nodes will need to perform the transitions in the protocol themselves instead they can just check the proof and make sure that this transition happened properly according to the specifications just as in the previous similar to the previous example the operations will happen now on Layer Two and in order to return to layer one we will have to uh certify this updated State using the proof and the certification is going to happen through a smart contract on layer one which will contain the verifier of the proof system

so I want to give you an example of how timization looks like and the one I picked uh is a toy one for accounts for account transfers and um but before that let's see what we want to get so we want to be able to transform this ethereum state function into a series of columns so a series of vectors which will be seen as polinomial and relations constraints among these columns so we just want to look at how we would artize this simple function the transfer and you can imagine for example you have like a center balance where the balance Remains the Same and then at the time of transfer we um we lose the amount and we lose the gas and then we stay constant again uh this is going now

this is then going to be a polinomial P1 of X in LR basis we can have a non column where everything is constant and then because we send the transaction now the Anis increases and then again constant a transfer flag that basically just says look now I'm transferring things a receiver balance column um that is like the opposite of the sender one except for the gas I'm getting the amount now and then everything stays constant and then some gas column where I need to store the gas and maybe you know have different modules that take care that ensure that that computation was uh made correctly and some amount C so the kind of constraint so as I said the columns are SE as polins I mean here

I say column but here they look more like rows uh there are s polinomial INR basis and for example I said that we want to have columns and constraints and example of a constraint is a binary constraint I'm just going to say look what I have in my column is only zeros and ones because this is a flag column and the polinomial needs to satisfy this relation over some um some a limited domain this is going to be a cycle group of roots of unity um but this is just like subgroup of a final field this is just a math detail and an example of another constraint if I want to look at the time of just after the transfer and time

before uh I can say look I want this difference to be the gas and the transferred amount and then I have more complex I can model more complex relations here this Omega minus one is is just a shift to the the previous time stamp um and then P5 of X Plus P6 of X is just the amount plus the Gess so we've seen obviously that doesn't model everything because this this is just like the beginning the giving you a flavor of how it looks like um but what you can infer already is that it's extremely complex and we're going to end up with extremely large columns for such a complicated State function but there are two advantages of

seeing things as polinomial Advantage number one is that if we use this schwart pal over finite Fields instead of having to check this relations between polinomial at every point you can check it only at one random point and the second one is that we have cryptographic polinomial commitments which allow you to give a sucin description of the polinomial and then infer make proofs about that um and then what you're going to store is actually going to be quite short and you don't have to have the entire thing when you reason about it so now we get into the heterogeneous part combining proof systems what proof system should we use um and in this talk we're going to talk about two of them um the first one is one that you probably

all heard of is plun over finite fields and pairings and in this case we're going to look at it using kg polinomial commitments the second one is code based uh here I'm going to talk about Varian that we have that we're using in Linea which is called wizard Arcane and the poal commitment is called Vortex but it's part of the same family of code-based um proof systems um like Starks and Fry and all of that and unfortunately we will not cover Lattis based proof systems because we won't have time so in terms of what kind of constraints remember we want to look at the polinomial The Columns and we want to enforce relations among them

what kind of constraints can we support in this wizard system that we have we can we have the typical ones we have lookups for example where we say all the entes of a columns are included in another column permutations all two columns are the same up to different order we can have local constraints where we're just arguing about specific points this is very useful when you're saying oh look this column starts from zero account just got initialized uh zero balanced something like that um and Global constraints when I'm talking about what happens over the entirety of the polinomial um and this is the one that we've just seen um where the polinomial gets shifted and on the right side I have amount plus gas um and this language is well suited for writing AR ariation constraints um

and the code based proof system is also going to be um quite well suited for checking these constraints efficiently so what are the characteristics of this proof system we have H paralyzation because um we use a hash function that is based on aesis um and then the codes that are that that are used areon codes which are linear so then in the end we end up with all the operations being linear or close to linear so it's easier to paral to to linearize them and paralyze them and then but um and the circuit size is going to be slower than in the case of plun so it's easier to U really go through a very very large number of polinomial and constraints but we have

some drawbacks first one is that the proof size is going to be larger than the one of plon and the verifier time is also going to be slow now let's look on the other side at PL circuits so now we're using pairings elliptic curs um here the circuits are are at the base level they arithmetic circuits additional multiplication Gates fan into and unlimited fan out that's how they look and um we can obviously Define more gates we can have lookups have permutations but mathematically when we write this complex Gates um it seems that they are less compatible with arithmetization than um than the code based ones um obviously this is not a a

constant maybe someone will come up with better uh better Solutions in the future but this is the situation right now so what are the characteristics of pron we have we're going to have small proof size um much smaller than wizard Arcane and Vortex I have a complex name for it but I think we need a short one um so much smaller than the code based proof system so it's more suitable for publishing the proof to the layer one um and the verifier time is also better it's a smaller verifier circuit which again means that it's better for layer one shorter to verify and also the smart contract is going to uh incur less costs which is quite crucial but the problems are it's really almost complimentary larger Pro time um

it takes um a long time to process a large number of constraints and also the pro circuit grows a lot then in the codeb based proof system so now the question of the talk is can we use the advantages of one proof system to offset the disadvantages of the other and the solution the answer is yes and the it's by using recursive proofs so complicated name but it just means you do a wizard proof followed by a PL proof what what what is going to be the language so for the wizard proof we're going to have the short commitments to the aration columns the statement is going to be my column sa satisfy the constraint system the witness is going to be the columns themselves I get my wizard

proof and then for the prong Pro I'm going to commit to the wizard proof get another commitment and now the statement the new statement uh the new ZK new proof statement is going to be that this proof uh this P wizard satisfies the wizard verifier circuit that's a new language and then the witness is going to be the proof itself we get another other proof the pr one um obviously in your system probably such a simple thing will not be secure probably going to need public parameters more complicated Machinery this is a toy example this is the uh the core idea and the verification is going to be only one invocation of the pl verifier um because it's going to automatically

have the also the wizard verifier circuit somewhere there inside so we call this Wizard and plun because it's a iteration of wizard followed by one of plon we're going to have small proof size this is going to be guaranteed by the fact that there is a plon layer at the end there going to be a better verifier time again because of the pl layer at the end and now we also have good Pro time because when we get the huge heap of arithmetization columns this get passed initially by the wizard which gives them to a manageable size um and the circuit size again is going to be smaller because this initial very hard part for the prover is being taken care care of by um uh by the layer uh yeah and the circuit size as I

said the yeah I'm just repeating myself okay so I have a small uh Toy example which is linked mimy hashes and in this uh small example I'm just going to Hash a vector uh so initially I start with the state of zero I hash the first element to get my first hash and then I'm use going to use that hash as um as the as a new state uh for the for the next one so H2 is going to depend on H1 H3 one H2 and so on that's my circuit and I'm going to um reason about this so what are the results if I'm trying to compare plun Wizard and plon and wizard um on this very small thing

at very small column sizes plon performs much better than both Wizard and wizard imp plong but again we live in the world of the evm so we have huge colum sizes hundreds of millions uh what about those and I have a benchmark for link memc so we can see the the Orange is just the code based thing um it performs the best but we say okay this is not an option because the proof size is too large um to to put on layer one and also the verification time is too large then we have plon which at the beginning on the left side before the graph starts actually is the best one out of everyone then as time passes is better than the

San line which is Wizard and pl but as we increase the column size it becomes really really impractical to to pass to to to to run the the pl prover and you can see that the combination of the two proof systems really stays somewhere in the middle actually closer to to the to the bottom at least for this to example so it looks like we really getting uh the benefits of both proof systems uh and in terms of the verifier Benchmark for this particular example it doesn't really make sense uh but just because of the way the circuit seems to behave uh but what I can say is that the verification time is not impacted and I'm almost done I just want to say a few words about other

implications of combining your proof systems one is trust assumptions um a code based proof system like the one with pluses here has transparent setup um that's super nice plon on the other hand has trusted setup so we need a trusted ceremony to make it work um and um but there are also other and what I want to say is that when you combine them you're going to get the worst assumption as usual in crypto and there's some other special cases to consider for example plon is really fast for some pre- compiles um and these are generally dtive curve operations so for e muad um our implementations have very hand optimal

um solutions for this and it's wizard cannot compete um so the takeaway now is if you have a very complex system it might make sense to use a bigger stack more complexity might give you lower costs uh lower latency lower everything you want um but it's not always the case if you have a simple system that doesn't have to deal with these huge sizes then maybe you can do your benchmarks and see oh this proof system is actually satisfies all my needs and is even the best um at this particular size and future directions that one can ask is do ltis proof systems also have like a particular Niche where they are

better than um than the elliptic curve one than the pairing ones and the code based ones and um also like for aggregation uh which one is the best uh I guess we can have an entire talk about that um and that's it thank you for your attention wonderful presentation Bon thank you so much do we have any questions from the audience today okay great Mike over here um hey thanks for the presentation uh so if I understood correctly you uh use plun to verify wizard yes right um so since you have well defined problem at the beginning right so the verification of the um wizard proofs wouldn't make sense to basically use the

old good gr 16 which is even faster and smaller uh it's a good question um I'm not sure I can answer it fully simply because I haven't uh I what I can say is we used to use gr 16 at some point in our stack and as time passed uh now we don't I mean we still have the implementation of it but we don't use it at least for uh for for our Layer Two um I cannot really tell you the reason but there is one right but yeah but you don't want to change the the Wizard right like once you have it yeah but then you don't do it every day if you do it like once a year then

you deploy a new verifier and that's fine sure yeah but you know there is the whole um initiative right to use this um you know double stage ceremonies so you can have you can benefit from it I mean again it's I think how often you want to do it and then you know at the end of the day we want to have a you we we should be able yes what we need to optimize in ZK for a real real world adoption is to have a very fast proofs to to generate obviously awesome any other questions yep over here I'll give oh nice catch okay do you compare it with

something like air SL fry um so for this I I haven't myself uh but I think it the team usually whenever something new comes up they always check it um so I'm pretty sure some other people did before me comparing with plun was not fully fair but you know yeah yeah I completely agree and uh it's something that I meant to say also like the the circuits are not even the same right like mean there are multiple way ways of writing one I completely agree with that yeah uh the point was not that the point was more we have to keep an open mind and combine things um maybe having a complex stack can really save

us so anyone else okay thank you our next presentation will go live at 12:35 thank you thank you