Proof Systems for zkRollups

foreign [Music] first part I will talk about some concepts for modularized proof system and in the second part I will talk about like how we actually improve system for our Decay drops and finally I will conclude with some like you know your your practical considerations when you are choosing this proof system so now let's start with the modular proof system so when you want to generate proof for some computation the first thing you need to do is that you need to do some optimization so basically like normally people call that circuit but but uh more formal word they call the constraint system and there are many different ways for the circular organization uh to give you some example for example in r1cs so assume that you have a huge circuit and you you put all the wires at variables and you lay out that as a vector like from uh like should be W1 to WN and then you lay out that all the witness as a vector so the form of rncs is that you can Define the linear combination of those the vectors of your witness times the linear combination equal to a linear combination so that's a form for one constraints enormous yes so for example you can access any any of those written cells um like using this alien combination but the limitation is that you can only have one multiplication so it's very good for for some programs for example if you have multiple like one large linear combinations but with a few like multiplication and so this is one example like if you want to access like cell like uh Omega one Omega 2 and Omega minus minus two and another example is that you can basically access any weakness cells using this r1cs so this is like yeah the form of rncs another commonly used optimization is called punctual organization basically what you can do is that you are not layouting all your witness as a vector but instead you you lay out your witness in a table like for example you have like three three rows uh and then like what you can Define that you can define something which is more flexible like for example you can define a a degree degree uh degree to degree three constraints like for example you you access some sales and then you define those as a very specialized case or specialized custom constraints and another thing you can Define that you can Define some membership membership relationship for example this Tuple belongs to uh like two columns in the table so using this you can you can do like range proof really efficiently for example you can have a fixed column and you believe that you you prove that this this element belongs to that table so that's another thing you can Define and the third thing you can Define is some permutation like you define uh like some cells are equal and so why this is useful because that in the first Uh custom gate when you are defining after defining multiple Gates you need to connect them together so you need this permutation to like for example Define uh the first case output equal to the second base gets input so those are three constraints you can Define in a plunkage optimization so it's custom gate lookup and permutation so from the modulus perspective uh there are three like commonly used front-end when the rncs as I mentioned like with which relies on linear combination and second is plankish which relies on custom Gates lookup and permutation and third is error which is dealing in Stark it basically contains like transition constraint which is very similar to custom case but but only a size two rows and also some boundary constraints for like defining your your starting point so that's the front-endable for for proof system and after you get this constraint system when you need to get a really you know implementable uh proving system like in practice you also need to pass it through a informational theoretical compiler so what does this mean so this compiler will Define some like interaction model between the program so in this information value compiler you only Define how the program and Wi-Fi are interacting and assuming that there is some Oracle where you can for example provide some message from Oracle and then verifier can like later query from this Oracle so there are nothing like you know concrete for example what kind of commitment you are using so you just send some message to the Oracle Oracle and the Wi-Fi can query so that's what happened in this information Circle compiler and so this is an example for interactive Oracle proof and the show from his IOP and another example which is commonly used is called polynomial IOP which the message is in the form of a polynomial like for example you use the p1x to represent your message and then like what a verifier can do is that during the query phase stage it can query at a random point to get this evaluation and you also do some interaction between the approval and the Wi-Fi you can do multiple rounds like which the like for example there is constant round polynomial IOP which for example during that like morning is doing that a lot of like uh stink a lot of proof system with teams of verification you are using this constant constant run polynomial IOP and then after you get this IOP to make that really practical you also need some cryptographic compiler to compile down to an argument which you know can be implemented in practice so I will give you an example so that's it so in this polynomial IOP like model uh one one pre-cryptal graphic compiler you can you can you can do that because there is a insurance active and you need Wi-Fi to send a challenge every time to the to the approver so what you can do is that you can initiate this challenge model using some free shamia and you just hush the transcript as the the next round challenge so that's what one thing you can do and another thing is that when you are because there is still a like magical Oracle there where you are sending this polynomial tool and verify can carry from right so you need to initiate what's happening here so you initiate the concrete polynomial commit scheme to replace this Oracle so for example there is qdg and there is Firebase there's Dory there's dark there's many on my commitment scheme so you just use those schemes to come into a polynomial and later open at a random point so that's you know after those those stages you finally get your your protocol so just as a summary for commonly used zero proof system you have front-end and you have backend so on the front end uh you have rncs plankish and error and on the back end you usually use polynomial IOP plus a polynomial communist scheme and uh a quick summary for the advantage between those different front end so rncs are really good for linear combination like what I'm saying is I'm specifically talking about growth 16. because in for example your marketing or Spartan or some other backend which also supports rncs it's totally different because it's the complexity actually lies on the super City for your foil Matrix so which is a different like you know uh like from for for evaluating the the efficiency and it's also more General because each constraint can access any within a cell like you do linear combination for that you don't need permutation because you know all the weakness are already in layout to a vector um and uh the plantation air stuff is more useful for some uniform circuits so uniform circuits that basically you have repeated structure and you can Define one custom case for those repeated structure you just need to increase the length of your execution trades and to to Really efficiently prove that and it's also more customized for example you have you can have lookup you can have variable like uh components so that's a front-end difference and on the back end what really influenced your your concrete property is that the polynomial communion scheme you are using for example it will influence your trusted setup whether you will have that and some security assumption and I will give some example later and also influence your concrete approval efficiency because like for example if you are operating over a group population it's less efficient than some scale operation and also proof size and verifier efficiency and some commonly used polynomial game is kdg flight based and some inner product argument which is derived from bulletproof and another called multilinear PCS so for kdg if you in initiate or your proof system with kdg then you you have Universal setup you have d-log security assumption and the proof is is relatively slow but but but but it's easy to parallel because it's mostly doing some multi-scale multiplication and the verifier only needs to do pairing and the proof size is really small and for Firebase you don't need to charge your setup and it's based on harsh do you use the Mercury and the resultant code to commit to a polynomial but but the tricky thing here is that when you are really unifying practice you also have some other like parameter Choice which will influence your practical security assumption um and the plural is mostly doing hashes and I have teeth and Wi-Fi is doing hashes and it has really large fruit but there are some improvements from for example 22 which can make the proof really easy to uh to to do recursion and for for the inner product argument it doesn't have set up because it's derived from bulletproof and it has dialogue assumption and verify are both doing remote scale modifications and you can use some techniques like pasta curve where you have two cycles to make that uh like easy to request and you have like a middle child proof and those are three polynomial commitments which are we are commonly used for committing to a univariate polynomial like it's a it only has one one variable but the degree might be high and another interesting Direction which at least blockchain people or in like industry people aren't really looking into it called multilinear polynomial communicate so it's usually commonly used in some check based constructions so some check it basically so this model linear polynomial commission scheme is basically you have a polynomial but you have n variables and you need to commit to this unvariable polynomial and then open at unrounded points and you can do some interaction to really reduce that to just one one opening so this is very useful for for many like schemes which I would introduce later um and so just to decompose some commonly used particles for example to use Plantation Planck IOP and use IPS economic means game or the community version is using qg and so basically when you are describing a a concrete protocol you can like divide that into to three three parts what kind of personalization you are using what kind of polynomial skin you are using what kind of like IOP or like the the information theoretical model you are underlying and started doing R and Stark IOP and some some fry use as this polynomial convenience scheme and unfortunately grow 16 is is not falling to this gate not for into this category because it's basically based on some linear PCP which you you do some like you you include some trapdoor in your choice is set up and do the query there so it's a very special case it's done for into this PCS modular like diagram and there are some new protocols as I mentioned like which is based on multilinear polynomial scheme which is showing one more like potential one is pattern which use RNC as the the front end it has its own IOP to handle this r1cs and the polynomial is IPA so the good thing for Spartan is that the approver is only doing one large multi-exponentiation so you can use GPU to really make that faster because it doesn't mean fft it doesn't need some other operation so it's highly parallel and then another new scheme called breakdown it's also already sales based and it's derived from linear time in Cold War code which makes your prayer time complexity becomes linear so it's linear to the scalar operation it's not two group operation and also another advantage of breakdown is that you can use arbitrary field for your for your weakness so one thing like even even if you are using Firebase one you you are only based on Mercury and harsh because you use resolvement code because you need so so you need to ffts a lot so you have to choose your field which is like has a large tool density to do in the life of teeth but breakdown can you using breakdown you don't even like need to like limit your field to be like fft friendly and there is hyperplunk which is from espresso and they do this plunkage organization and hyperplunk IOP and you can use kdg or a freight derived like multilinear polynomial communist scheme which has some like potential and uh there is also Nova and uh so for Nova like you you can't actually really fit into this IOP diagram it's it's RNC space it's really good for doing recursion and when you're doing repeated computation you can use normal to do recursive really easily has some nice property there but unfortunately I do say like those multilinear uh polynomial scheme are most only support rncs front end so which that's why like you know hyperplunk brings you this interesting property where you can define something more customized now after talking about the proof system let's look at take a look at what we are using in the key drop so the idea behind the cutoff is that you send all the transaction to one layer to proverb and this layer to prove our generative proof and some music proofound chain with some necessary data for verifying this proof and so the proof system really matters in zikr right because the approval time your approval cost your proof size or influence your the money you are spending on each transaction and also verification cost which which influence your guests you're spending so now let's take it let's think about what proof system we should use for for such a general purpose liquid rub so as I mentioned like you first need to to know that what you are really proving so what's what's computation you are you are executing so for General general purpose uh like the Hero app you are actually you are actually executing the evm execution logic so you need to think of evm as some type of computation and you need to prove that so to constrain this evm virtual machine you have multiple like uh limitations for example your evm word size is 256 unless you use some Rim based structure it will always be the non-native field so you need some efficient ring proof and there are some they can unfriendly op codes which means you need some specialized circuits and then you because if you put everything in the same circuit it will be huge with a large requirement for the memory and for for the machine you are using so you need to decompose the circuit into different types and you need to eventually connect different components and thirdly that is a virtual machine circuit so you need read and write efficiency so you need some kind of efficient mapping from read and write and also like one last thing is that evm is very different from static circuit you are using for for some fixed program because the execution Trace is dynamic like because different transactions have different trades right it fills up this this table like even in the same position it might have different op codes you are approving so that's why like you might need some like efficient of selectors so the first three drive us to your circular animation how to support lookup because you know that you have e Vision really prove there you can connect circuit there and also you can do this efficient mapping and the last one drive you to some more uniform presentation for a circuit you are defining some IR in between two for the four instructions and also select that some at the point you want so that's the reason why like we have to use pancake customizations or start based because they can also support something more customized and now let's take a look at the event we are actually using so in the KVM we have like two layers one layer is proving the evm logic directly for example it contains event circuit to prove the stage transition it contains a ram circuit to prove the read and write consistency story circuit for State update and other circuits for example ecds is okay for Signature and some other circuits and they are directly used for proving the evm itself and then because you result in so many proofs so you have an aggregation layer which okay aggregate mobile proof and into one proof so one way of thinking of how how we are treating the full system uh it's actually two layer so think about the requirement for the first layer the first layer really need to be expressive because you need to express really large circuit and so that's why like you have to support custom gate and look up smart lookup lookup tables and also you have to use some Hardware friendly approvers to lower your approver cost because you know your input computation will be the largest one you you are directly handling evm evm not the the verification so that's why I like you know you need some Hardware friendly approver by saying Hardware friendly there are two things one is paralyzable and second is low Peak memory because you know if you have low memory then you can run a very cheap machines um and also the verification circuit is relatively small because you get so many proofs and you need to aggregate that in the second layer and the ideally there should be transparent audio Universal setup because uh you might add some new pre-comparents as a new circuit to this existing diagram which makes the the whole the whole thing like you know if you are even closing you have to do setup again again and so there are some promising candidates for example plunky 2 30 and they are using right to do this like really efficiently and there is a hero tool but but you know for the kdg version It's not that promising because you know although the the verification size is very small but it's on another field so one one potential is that you can still use the passer curve for Halo 2 doing all the regression for your the evm and the content a lot of like prove a lot of computation and then use something like a bridge to bridge this Halo to approver verifier to your final verification and there are some new iops without ffts because I have t you need a like large memory and uh it's less parallel for example there is hyperplunk there are some new constructions which remove fft in your PCS and so that's that's two promising candidates and also there are some some check based particle and like by design it doesn't have ft it only involves some group operations so for example Spartan Virgo and all those those constructions or Nova but unfortunately the only sport rncs so if one day they can support Punky stuff then like you know it will be more easy to use and in this in the second layer uh as I mentioned like because the requirement is actually uh efficiently verification on evm so even if some Wi-Fi is efficient if it's not an evm then it doesn't make too much sense on for for the key drop so and also the the second secondly that you you need to prove the verification circuit from the former layer efficiently for example like if your formal layer involves some non-native stuff then your second layer is better to support some funky stuff because you need some customized stuff to handle your verification circuit and ideally it's Hardware friendly and ideally it's transparent or Universal I said ideally here just because it's not a very harsh requirement because you're the largest computation has already been done by the circuit first first layer and then like for the aggregation circuit you need to do like smaller amount of computation so that's why like maybe not the uh the big stuff and so some problems in candidates is that when they grow 16 which I think hormones are already using practice and second choice is actually Punk with very few columns for example we can configure that to be just one of one otherwise column one lookup and one fixed column it can be even sometimes even more efficient than grow 16 like you use kdg or you use F1 proposed by the Aztec team which you the trade-off is that you uniflunk you might have a like more efficient verifier than grow 16. but the truth of it that you you triple your print time and uh and also there's fry which with a large code rate and which you have a smaller verification circuit and you can yeah you can basically do verification usually so this is like our our construction we choose the first layer to be hello to and second layer also Halo 2 but the hash function uses is different because it has those Nest properties uh since we are running a little bit of time I will just skip this right and so it's just basically good performance with GPU approver and the notification circuit is more since it's distinct and the second layer is that you know because you need to prove for the first layers like verification you need custom gate and uh so there are some future work we are like actually thinking of and I want to have some special is that we want to generalize this framework a bit so uh we believe that the front end logo of the front end will be pillow too because it provides really flexibility for writing circuit like you have different rotations you have different layout configurations so we we want to generalize this framework to to support using the same Halo 2 front hand but for different polynomial iops for example like hyperplunk IOP and for you know you can add fry to the Halo tool and also like we need to significantly improve the hello to tooling sport like because I heard a lot of complaints from developers who are really using hello to like you know might be there might be some DSL you need and the bug reporting is really poor and other like you know any feedback from from developers who are really using that and one last slide um I will talk about some other considerations even beside the efficiency for proven Wi-Fi so there are some concrete considerations here first is your ecosystem so if you are using a zero and approved to develop your application one thing you need to to think about is that whether it's compatible with existing libraries so if you for example and whether so there are so many projects and gadgets implemented there because for example if you want to just build a simple application if there are so many Implement gadgets you can directly use that which can simplify your demand process a lot so that's what I mean by ecosystem and second is implementation so even if some new paper coming out with very very nice complexity you still need to think about what's a implementation how long does that take for example like industry implementation is usually like more solid than with better performance and better security consumption like considerations than the academic one and you also need to consider the best practice like for example if you are running a benchmark it shows really slow but if you know from the algorithm side that is very easy to parallel using GPU kernel then it's not a big deal and also there is license and audit and uh so if we can really standardize the the framework for for the proofing we're using and we will have a very large community and even have this specific for making this kind of proof system faster and making that really great so I think that's that's pretty much how I want to cover and thanks for for having me [Applause]