zk Academy #9: zkProof mechanisms with zkBob, presented by Union Build

Transcript

[Music] [Music] [Applause] hi I'm Vladimir from ZK Bob and today I'm today I'm going to talk about the SN based wallets uh first couple words about what is zkb it's a smart contract wallet that utilizes growth 16 improving system to enforce the the validity of uh user

balances uh we'll talk a little bit more about um which circuits how it is used um in more detail later uh but uh first we'll talk about the growth 16 itself we've been in production for years here now and um I would like to share some knowledge uh with we we've gathered first of all uh a little disclaimer this talk is intended for uh the audience of total beginners um whether you just uh know the Sham school math and that's it and you want to have a sneak peek under the hood of the mathematical uh techniques they used to

construct Z nors and particularly growth 16 so the problem is following we have a program that requires too much resources to compute or may have some private arguments and the prover wants to execute the program locally and present a proof to the verifier that will convince them to that this execution was indeed correct uh and um the third and um uh maybe the most important requirement is that these uh verification step uh should take less um less time than the execution in program itself and the

proof might must be shorter than the program uh this word shorter is indeed a a rabbit hole of itself and uh I don't want to uh get into too much detail here but the idea here is that if you have a very big program you you wouldn't want to re uh reexecute it and you don't want to share all the parameter parameters because uh the uh parameters itself uh can be very large a very toy example of such a program can be checking the relation between size of Pythagorean triangle

where you have a public value of H hpen C and you check that you know such catei a and b that they relation between wellknown relation between the sides holds where a squ plus b square is c^ squ U by the way the uh problem of finding a is believed to be hard because it involves uh factorization of C of course the problem with checking is uh easy but like it's very Visual and it will help us go through the transformation of this program step by step so let's go um if you have ever used or seen

um any framework that uses for writing circuits for ziki snarks uh then uh the program would be something like this and it's transs quite literally in in the code here's example for the folks crypto framework but like this talk will help you as I said have a sneak peek under the hood how this math is um actually um executed so first things first we create a So-Cal circuit uh this is u a structure that where you have uh all the inputs public inputs and secret inputs

on all the intermediary variables put together in so witness or assignment and you have um all the operations grouped into so-called Gates where you have multiplication Gates and addition Gates and um all the outputs are the result of a single multiplication between a left wire and a right wire and uh arbitary addition multiple additions so um I would say that this step is kind of optional at and it uh is a more of a mental exercise than it's useful for development but the terminology used here such as signals

Gates and circuit itself is um used throughout the industry and it's um basically in the circum uh it's uh very inspired by by the electric circuits so maybe it is helpful uh the most important thing to notice here is that every output is the result of multiplication of the left wire and right wire next we'll transform this circuit in a next concept called uh the rank one constraint system it looks very busy but in effect it's pretty much the same thing but in very sparse representation you can see here that we

have the pretty much the same relation between the variables such as a * a is a squ B * B is c s and so on but all the zero zero signals or zero inputs in every gate are more explicitly presented what we do next is we can transform these equation into the table which are um my opinion it's a little bit more visually um understandable uh so we see here is um if any variable is um whether a specific variable is is um involved in

in a calculation of a specific gate for example we see here that for the third gate it's fourth gate but with index three uh the uh variables a squ b^ squ uh the variable one which is default input uh and C squ are involved whereas uh a squ B squ is left input sound and C squ is the output um these matrices are like the essence of the program it uh it dictates how this program is executed and how the proof can be checked against uh as you can see here our relation between the left wires

right wires and output are not uh satisfied here so for the third Gade the uh multipli ation doesn't give the expected result because it lacks the valid assignment so let's recap what we've done so far we have this circuit is a representation of the code itself and we transformed it is to three matrices of that show whether the variable is involved in calculation on setting sting gate this is a common knowledge between prover and verifier which uh which is like a contract that will help help them um to generate proof and to

check it next let's assume that that we have as approver have a valid assignment for this problem um so the Cathy is three and four the public hypotenuse is five and uh other variables are 916 and 25 and as I said the default constant input is one so right here we see that the relations uh now hold that 9 + 16 * 1 is indeed 25 and um it holds for every gate next what we will do now is we want to squeeze all the tables from the sides to make it uh a little bit more concise

and easier for the verifier to check because we want the fire to do as less job as possible so so uh we moved from the element wise multiplication of the scalar products to uh element wise multiplication of vectors such as the L uh to the right here you can see that we just removed all the zeros from the table and summed up all the uh rows I have uh conserved all the uh uh colors so you see the three and four and five and uh 25 is the sum of 9 and 16 we will do the same thing with right wire

and output wire and we will see that the relation still holds so all the multiplication are still valid uh why would you do that why would we want to have the such a vector this is because we can transform uh these Vector of topples into a polinomial for example uh if we interpret every topple as a point which is like a topple of coordinates we can create such a polinomial this is called interpolation it's a very well wellknown algorithm it's uh very widely used uh here the interpolation is made in real

numbers which is uh not the environment that we're working on uh in fact we're working in finite fields and the polinomial of course would look quite different but but uh it uh suits our purpose of visualization so let's recap Once More we had with these three tables we squeezed them to make three vectors and we created a three pols that um have the same relations as before uh next we Define the our main poal P which is the result of substraction between between uh

multiplication left and right wire and the output and um our three polins are transformed to a single polinomial and because our valid our assignment is valid and uh on every gate we had a zero then our poal P must be zero at all all the gates at each gate and vice versa we can say that if the Pol p is zero at each gate then our assignment is valid uh why do we want to use the polinomial in the first place because polom has have very uh unique and cool features such as that we

can um determine and a unique polinomial using the toes which we used of far the is the interpetation and if we have evaluations of two polinomial then a polinomial which is the sum of them has the evaluation which is sum of evaluations there are other very useful features that we will use later such as that if the polinomial has a root Omega 0 then it is divisible by x minus 0 and also the evaluation of polinomial is just a DOT product of coefficient of powers of Po of the variable and also uh two pooms of degree D such no more than

D points so we get we got one step closer we had our circuit we had transformed it to three pols and then transform it to a single polinomial with uh with zero at each gate so our statement about the Pythagorean triangle transform it into knowing a polinomial such as this one of course again in finite Fields it would look different but it's it's pretty much uh okay and suff for now um so since the p of X is equal to zero at each gate we can um represent it

as a multiple of something some polinomial H ofx and all the monomial which look like x minus um Omega I where I is um represents all the indices of the gates these um product of x minus Omega I is called The Vanishing polinomial because it indeed vanishes on at each each gate so our statement about the P of X being zero at each gate can be formed into a an existant of such an polinomial H ofx which is called quotient polinomial

let let's again um reflect on what what we do done so far we had our circuit we translated it into the tables of inv variable involvement then we had our um uh polinomial which represent the interpolation then we had transform it to a polinomial which is zero at all the gates where then we transform it to a poal h which exists only if the assignment was correct as you can see this polinomial H gathers both the essence of the program because it was

created using the uh matrices from the circuit and it also exists only if the assignment was correct so it has these both things this is the sage code just if you're interested to reproduce the graphics so how is it verified so apart from the uh P being zero only at Gates uh the divisibility property must hold everywhere so we can also check it everywhere so if we have a single point tow we can check the that um H * t uh is indeed p and

that that would give us that the assignment was correct the problem here is that if prover knows the point where these um property is checked then it uh they can very easily cheat because uh they can create such H so that this property only holds at this single point and any nowhere else and uh this way the the the proof will convince the verifier although the calculation was not made correctly and it doesn't hold each gate so the problem is like uh so we would like to make the tow random uh

which is which means that it is unknown for the pro be beforehand and then if if it is indeed random then the probability that it uh somehow very got very lucky and um uh that these equation will hold is uh 2 * D divided by P because where we have D Gates in the circuit and P is number of elements in our field which is very low number so the problem is how do we make it this uh Tower random and unknown to anyone else um fortunately for us the elliptic curve cryptography uh offers a way to

encrypt values by multiplying a scalar tow by a point G which is called a generator so and the problem of find in towel where you have G times tow is known to be hard so um the idea here is that having uh if you if you have to calculate evaluation of a polinomial you just make a scalar product of dot product of the coefficients and the powers of the variable and now if we if we have the uh inced powers of um variable which is to

so we have to calculate the evaluation at Point um G times to we just make the same dot product of the coefficients and the vector G times t to the power of I for all the gates so now we have to find this Vector somewhere this thing is sometimes called the trust setup ceremony uh in Z was even called the powers of tow there is Project called Perpetual poers of tow so it boes down to um lots of people coming up with random values like as random as they can be uh then they calculate this

Vector of encrypted powers of tow and all add these um results with the previous contribution so um if at least a single contributor is honest and it discards all the values uh after the procedure is complete then the setup is believed to be secure um the result of such a ceremony is called common reference string or standard reference string and it contains um uh powers of tow and some other things that we will talk later uh this is the paino of growth 16 and we later

to so after having uh the evaluations of our left right and uh output wires and um quo polinomial we would like to check the that indeed relation between them holds but the problem is that we don't have such an operation as multiplication between elliptic curve points but what we have is uh solal pairings it's very complicated topic on itself uh and um uh the intuition be behind it is that it's basically like an uh uh multiplication between encrypted values uh where you can do multiply just two values and no

more you can just have multiple uh multiple variables multiplied at at one time this is why we had these two multiplication wires in the first place but also uh that would make if if we had if we would be able to multiply more than two variables at a time uh it would also break the protocol because uh we could make the um New proof based on an old proof uh without having to executed the program itself so what we did here is that we uh transformed our program uh which operated on tow to the encrypted

version uh we moved the output evaluation to the right hand side because subtraction in pairings is uh hard so now we have just a single relation that a verifier needs to check and uh that would convince them that the assignment was indeed correct now the whole protocol is the following we create a proving key which is uh a setup step which is the powers of tow and the encrypted evaluation of um wire pooms uh and uh verification uh key is just uh

the generator um proving involves just calculating the uh encrypted version of uh calculating the the polinomial for Left Right and output wires respectively then then calculating the quo polinomial in coefficient uh form and then then uh calculating it its evaluation and sending uh all the left wire encrypted evaluation white wire encrypted valuation output and qution polinomial to the verifier so the verifier can check just these single relation and it

shows that the assignment was correct um I would say that like there are some uh inaccuracies here that was made by intention to for the SEC yeah we me so far so we we also um apart from uh being uh the calculation being correct at the every gate we also need to enforce that uh every single variable that is used inside the circuit was indeed the same so we we just didn't uh for example replace uh 25 with some of some Rand values so uh this is why the U

not just the uh capital L evaluations are are included in the um in the proof but like we have to include in the C CRS also the evaluations of the um so-called apparent polinomial uh little l r and O which basically enforce that uh all the variables are indeed on on their place and uh this is the big biggest problem of gr growth 16 I will talk about it later we also have um uh we also have to ensure that uh the approver hadn't used

any random V uh accept the ones that were provided in the CRS and this is this is why we have in the version of protocol we would have an extra step which is called checking the alpha shift where you have U uh some more parameters like this like random um Alpha multiplier and uh you would have to check the relation between the evalation of a wire and evaluation with W of the wire uh multiply by Alpha in crypted domain um I wouldn't say that it changes the uh the protocol very much so I have

admitted it yeah also we're working in Prime field module p uh and also there are very uh few curves that are efficient for pairings uh which are also called s friendl or paying friendly curves uh and um which which is a very important thing to know from compatibility compatibility standpoint also this Omega I thing that we use to inate our gates is not just a regular natural numbers they are inde the So-Cal roots of unity it's a special number in multip multiplicative

subgroups um where is um uh Omega to the power D is uh one so this um um this uh T polinomial is very easy to compute and it also enables some optimization features such as fast for Transformers yeah and one last thing is that public inputs are calculated by the verifier but it doesn't make any difference also yeah you would ask where is the zero Lo stuff because we had these um private inputs to the Circuit A and B and uh it seems that these inputs are somewhat leaked because if we generated

two two distinct proofs for the um for the same values uh the verifier could find it out so uh surprisingly uh thek stuff is um optional and it can be added as a as extension of the protocol it basically um adds Some Noise to all the variables uh it's random variables that are generated during the setup phase and by the prover and uh the idea is that you uh multiply or add something to the both

hand side right hand side and left hand side of all the equation so the all the relation hold but but the uh verifier doesn't find out anything about the initial inputs yeah so uh how is it this protocol can be used in the while since uh 2020 there is a dedicated promile contract on evm chains uh with um uh the BN 254 also called albn 128 curve which allows uh efficient pairing so you can basically write a smart

contract uh that verify verifies a growth 16 snark or or not even growth 16 everything that uses ping on this curve uh we have U multiple of dsls and Frameworks and libraries that help you write a circuit like this uh we we are using the cable B uh the Balman prover and uh for writing circus we we use a framework called folks crypto which allows you to U both generate a solidity contract as well as compile the pr to wasm uh make bindings for nodejs and uh Native comput Native

binaries also so how can you use this uh the most popular things right now I would say is uh the proof of set inclusion you can basically do verifiable credentials such as polygon ID or you can do something like a proof of reserves which is was um uh I believe made by binance to uh prove that they have reserves for all the U client balances uh zash also uses them for their sh transfers and of course ZK Bob also the

second thing is uh proven signatures checking signatures so you can prove uh the signature in inside the snark so without revealing the public key itself and U of course you can check just arbitary mathematical relationships uhle that balance is sufficient or that the player has value coordinates inside the game world or anything else as we have seen in our example so uh couple more words about how it is used in ZK Bob as an example of the strong based SM smart contract wallet so we have the U transaction

commitment which basically has um all the information about the uh transfer of the draw of the deposit that clients makes and um uh inside this circuit we will'll do several checks I think I have yeah uh so what we check is that if we spend or transfer the um a some funds uh we check that ITA signature for the transaction is was made correctly um without reallying the public key that the client uses we check that the balance is sufficient and we check the

uh that the account and the private notes that they user in transaction were uh indeed in the anonymity set um yeah this is how the uh basically the state of the application looks like you have we have uh the private uh private State or the that is stored on the client which is like the lower thing uh which basically is contained inside inside the transaction commitment and we have a public state which consists of just meracle roots and account fires and every time a transaction uh is uh made

we ensure that the commitment is correct uh the sequencer um includes this in the Merle tree and uh it uh um accompanies the transaction with the proof of these correct inclusion so we enforce that U all the transaction were indeed included and all the transaction are indeed valid so about the growth 16 comparing to other protocols um there is a hm Mark of the protocol which is uh that you can um check the validity of the huge program using a single curve point point which is encrypted evaluation of

H and um uh the the proof is a constant size and it requires a constant um amount of operations but uh it yeah it is also the oldest and the most B tested I think protocol so there is quite a lot of tooling uh available such as circum as I say um zorres um folk crypto um artworks and so on uh cons so yeah the main um the main downside of uh being able to check a

single point is that the circuit is basically uh hardcoded in the setup phase so every time you want to ship a new uh circuit you have to do a u setup which is U basically very hard from security standpoint because uh it's a big coordination problem um I don't know if it's good or bad but like some users don't really care if the TR setup was made correctly or not uh I personally would like to them to care a little bit more but uh from for from the

professional standpoint the setup is a very questionable thing of course the other problem is uh the parameters so the CRS is huge it can be like hundreds of megabytes or even gigabytes so uh it's not that CR critical if you have a b roll up sequencer uh but if you uh force your user to do these parameters in order to make proofs they can be a huge problem um also uh there are very few curves available right [Music] now um maybe just on evm chams or not I don't know for example the BLS uh

12381 curve hasn't made it yet to the eum the uh the EIP is uh stall for a couple years now so there is only just one curve that is available on AVM and this is the problem of all the uh snarks that use bearings so what's in terms of adoption I would say that um if we assume that the Privacy is required for adoption then um it's basically done and we have an application that allow users to transact

private uh but also um there are much more than to to be done uh basically we want we want these private applications to be able to um cooperate with other applications and institutions the ux must be really good and uh for the users to uh to move from the web to applications to the crypto and also there is like a gray zone right now whether we have to disclose some information about this transfers are not so some more detail details about these so the main uh problem with uxx is

that uh the the the bigger the circuit is the longer it takes and the more Source it takes for the from the prer and it's very crucial for mobile users and and um I would say it also applies to using Hardware wallets of course and um the main bottleneck here is soal multiscalar multiplication uh which is researched quite quite quite actively right now and there are certain directions such as U from uh engineering standpoint and from uh radical

also uh quite a few words about this uh if you remember we had these multiple um pols for Left Right output wires and quotient polinomial that we had to uh basically evaluate in the encrypted domain which is the dot product and this dot product thing scales really really bad and group operations which is multiplication by of a point of scaler is kind of hard and the problem is that we have to do it um lots of times and uh there are certain

approaches uh that can be adopted such as uh watch one of the most popular is so-called uh bucket eding approach where you can um basically divide your 25 250 six bits um numbers into a lower bit limbs like three 30 16 or something like the bits and then uh it creates a so called buckets where you these uh every limp has only two to the power C uh possible values so you just throw uh the some of these points into to a

respective um bucket yeah another problem is uh the um ux and compossibility problem is that the address system uh between the ethereum and um private wallets is uh non-compatible and so you cannot use for example um the centralized exchanges to withdraw money or fund uh or deposit the money uh and also um because of the many in incompatibility incompatibilities you're um forced to

use the uh dep itself to store your private data and keys so I hope in the near future uh World extension such as metamask snaps will help uh at least with the with the problem of the storing securely the keys and data and we will see in the future also if uh the problem with the addresses in capability will somehow solve yeah another problem is that there are lots of cryptographic Primitives out there used for mostly authentication uh such as uh um a Ed

25519 which is used in lots of protocols and uh for example web o n uh cannot be used inside the snarks so for example for the signature in check in Z Kebab we use dedicated curve uh introduced also by the fum Foundation which is called baby jobjob and uh it's it's special kind of curve that is could could be used inside the snark and most of the other curves are not not that efficient to use there are some gadgets that you can write uh to uh work around the things like this but

it's um very inefficient unfortunately yeah another problem for for private wets is the state synchronization where if you have a collection of private input you have some history that is store on chain uh there is no way to uh somehow fetch it in uh single request because you would compromise your an anonity so you either have to brute force uh like try to decre or something like transform and find out if it is yours or not or you have to try some third party and unfortunately I haven't seen any uh progress with this thing uh Al although there there are some um

there are some papers which try to use fully H encryption for the things like this uh there is no practical U thing that that could help is as far as I know and uh the individual problem of the growth 16 and for us uh is that shipping new circuits is uh really a pain point uh and um we have just three circuits and introducing a new one is always a huge problem um and I hope that the system like uh plon and all the fa flavors of plon uh will uh get better

throughout the years and uh we ALS I also hope that uh some system that um introduce um recursive proofs so that you can have U not that lightweight verifier uh as in growth 16 uh but it is deployed not on the main net where the purification can be very costly but it is deployed somewhere L2 and it's uh the the proofs are aggregated or folded so that it costs uh less um yeah and the last and but not least uh there is a problem with the

Privacy application that uh we don't have uh certain requirements about uh what private arguments I mean what private data has to be disclosed or what is not we have uh our view on this problem of course and we have special opting compliance features such as a compliance report where you can uh decide to disclose only a certain period of uh your transaction history without compromising nothing that is outside of these period there are also other approaches such as privacy pools that use these externally provided

Association sets so that you can prove that your funds uh were indeed um one of the checked uh deposits and uh not associated with Harish for example there are also some very interesting Solutions uh that are being developed last years some like polygon ID which is privacy preserving verifiable credentials that also uses growth 16 and uh Merle root Merle trees so this is it uh there are some links which with interesting materials about the growth 16 and not and of

course about to keop thank yeah awesome presentation Vlad um we still have a couple minutes for sure so I'd like to ask uh some questions about some things that caught my eye and I'm sure Rob is being a mathematician and math degree guy he's probably itching at the chops too but I just want to go first because I know that you guys are going to take it over after so uh on on the slide on circuit and transaction commitment I've been doing quite a bit uh of research into um the world of yeah the um I think it's yeah it's the slide right before the the circuit and Merkel route one so it's towards like the like

the second half there okay pull it up yeah I've doing yeah yeah it's um it should be just right after those ones this one right so I've been doing quite a bit of of research on sequencers and kind of how their costs of of rollups work kind of what the business model is um you know how they how they operate and So based on this on this um operation here um basically what we have is that there's a a a new transaction being created um and basically being verified that it is uh uh indeed correct um and so coming on to to the next slide

we have uh that the the sequencer proves that this new Merkel route is uh indeed correct and corresponds to that set of commitments now in this part where it says to help offload part of the work from the contract and client is that a a is that an economical reason is it a technical bandwidth reason um is it because you can store that data off chain you don't have to pay to store it on chain kind of what is like the the reasoning behind multiple reasons yeah okay there are multiple reasons uh first of all the uh sequencer uh eliminates the race condition between different clients because if there there were no uh

sequencer then um like the sequencer is like a point of secularization between clients otherwise the like two clients that would uh try to create the uh the proofs uh for the same Merle route they would they would create like a race condition and uh the person who uh postes uh posted it uh then they would of course um get in the in the conflict with each other um other than that uh of course there is an optimization thing that we don't want to this thing to be

calculated on the client also and the third thing is that we don't want to uh the the tree itself to be stored on chain we we don't we want to only the in the calculation of the mer root we don't want to to do it on chain uh because the we use the bid hash uh because it's snar friendly thing and uh it's uh rather expensive to calculate on on chain because it involves uh it includes um also hard hard operations I would say so

yeah yeah CH jar is that it's it's expensive and uh it um it requires more storage and uh it also creates race condition yeah makes sense block space is valuable thanks for the answer pass it over to Rob thanks uh great presentation Vladimir um my question is about the multiscalar multiplication um you mentioned that accounts for 80% of the computation in the proof so this is like the moon math that everyone everyone talks about like this is the ZK proof Moon math that everyone

just kind of like trusts but doesn't really verify and I think part of the reason of that is because it's it's like complex and it takes a lot of computational work so my question is like how this applies and and how we can choose an elliptical curve that makes the most sense for this Moon math like you mentioned uh I think it was BLS and you me few curves there's a few of them out there like why do we why do we choose certain curves for certain reasons and is there like a general purpose or is it more of a specific purpose on why we choose certain curves um and then where do you think like that

that direction is going so first of all the the MSM thing itself itself is not that uh I wouldn't say that it's complicated uh the all the like algorithm algorithm are pretty uh simple but like the the question about the curve is uh kind of tricky uh so uh there is a question of security of course uh and there are certain teams and researchers that create and find out all these new curves and this is like a bottomless Rabbit Hole uh of its own it's a very complicated thing um you can

there there is a very concise tutorial about the uh BLS 123 381 and the U you can which is called BLS 12381 for the rest of us and it's a concise form but you can uh estimate how hard it is uh like to to find and estim security of the thing so um yes uh different curves have different properties uh like for example these curves have are pairing friendly which which means that they have some uh thing like like curve extension embedded degree or something

like this this is like indeed the moon maath and U BLS also has this property of U it's called like endomorphism which is uh can be used to um make the MSM uh much more efficient and uh uh uh unfortunately it's not as I said um it's not supported by AVM right now but only the BN 254 is is supported but it doesn't have this endomorphism future basically what is endomorphism is is a way to uh better

predict what will be what would be a result of multiplication of uh scaler by a point uh because uh on the most of the uh curves uh it's it's completely random thing which is uh how this was invented in first place and there are certain curves where is not so much random and you have some pre-processing thing that can speed up the uh MSM but uh unfortunately none of them are right now supported like uh again tldr nothing is uh is static and we can we will see more curves later and

we will see more curves uh I believe supported by the public blockchain platforms and networks and uh I think U these the initiatives like Z price that pays a huge amount of money for uh speeding up the MSM uh and also other approaches as well uh is helping also yeah amazing cool makes sense uh and there's there's blockchains like zcash that have used like certain certain elliptic curves and then uh like like you said there's multiple blockchains that use multiple different curves for

multiple different reasons and we'll continue to see more chains and more curves uh for their use cases yeah yeah zash team is as far as I know the zash team uh invented did uh some maybe like just a new family of Curves for the their future upgrade to hello 2 h Hello 2 is like the next thing from the same team that come up with the uh the sapling protocol which is uh what is a Cas based right now uh it's a transparent uh Zar which means that it doesn't have need the trle setup ceremony and it still has very nice

features for um standpoint of proof size and verification time and um but they have like again they have these uh nice new curves which are not supported any else but maybe that will change in time yeah I'm curious to see if they can integrate somehow with some of these other curves that are more widely more popular um and widely adopted on ethereum we'll see we like the curves thank you so much for for coming on vad it was it was a pleasure um very very insightful and learned a lot thank you thank

you