ZK12: Distributed proof generation for zkEVM from code-based polynomial commitment schemes

Transcript

[Music] so hello everyone today I'm going to be talking about scaling of proof generation and I'm going to present several techniques that can improve the efficiency of this process for the case of snarks based on the proximity test uh for the read Solomon codes so let's get started my talk is mainly devoted to two problems they are distributed proof generation and incrementally verifiable computation in the first case we have a large computation that is distributed among multiple provs and their goal is

to produce a single proof that guarantee the correctness of all their local computations in the second case we have a long running computation it means that the input of one prover can depend on the output of another and moreover the such chain of computations can be infinite let me give one motivating example so let's consider a multi-chain system where multiple independent blockchains operates in parallel and let's assume for Simplicity that blocks are produced uniformly over time then our goal is to produce a state transition proof I mean proof that

current state is correct If the previous one was correct proof uh State transition for each separate chain can be proven by separate Pro and it means that we can think of this process like a distributed proof generation and contrary if we want to obtain a single proof for a whole bunch of blocks we need to into account recursive nature of adding new blocks and this is a situation which is perfectly captured by the notion of I VC now let me go back to the first problem namely distributed proof generation so we have a large computation C which is split into

several equal parts and there are several provs each which operates on its own part of the of uh the whole computation also we allow provs to exchange data so that they can produce a single proof that guarantee that all their local computations are correct simultaneously we can achieve uh efficient protocol for this problem using additive commitments using them we can obtain a commitment to a linear combination of data without actual direct access to this data but fry protocol is heavily relies on cryptographic hash functions that don't

have such a property and that's why uh this this problem for that case is so challenging basically many protocols use uh require to send a huge amount of data whose size is comparable to the size of the local circuit and there is another extreme approach for the fry based snarks where every prover can produce an independent proof then we can so given this multiple independent proofs we can aggregate them all together into single one but the problem is that the size of the recursive aggreg the size of the aggregation aggre um aggregation circuit will uh will grow linearly in the size

in the number of provs so um before I introduce new approach let me briefly recall how FR Bas snark works so we assume that our computation is represented by our execution Trace is represent is represented by a set of polinomial then prover uses the re Solomon code to encode these polinomial namely he computes a vector of eval evaluations of this pooms over the large domain and then he computes commitments send corresponding commitments to the verifier and and the most expensive part of the verifi drop is to check that

these commitments are correspond to functions that are close enough to the read Solomon code and in order to to do that uh parties execute budged version of the fry protocol namely uh prover gets a random Challenge and computes a random linear combination of his local polinomial and then he executes a regular version of fry for with with this polinomial as an input since verifier accepts during this protocol we can guarantee that this linear combination is close to the read Solomon code and it means that each of the initial polinomial is close to the

to the read col Solomon code as well so so we propose the following approach we also allow exchange of data but we use this interaction to compute a single linear combination for all the polinomial across all the provs and in order to do that in order to minimize the size of data to be transmitted every PR computes a partial linear combination in order to do that we introduce some kind of synchronization between provs so they can compute a single random challenge here uh I should make a reference to the paper on amortization techniques for fry based snarks which

also uses a single linear combination in order to minimize the size of the final proof but the main difference is that we are working in distributed settings which imposes different different limitations uh on our protocol so here is more formal view of our protocol so at the first step prover computes commitments to all his local polinomial and sends his commitments to the master approver which in turn derives a random Challenge and broadcast it to all the provs given given this random Challenge and specific Powers Prov can uh prover is able to compute partial

linear combination and you can see that there is just a single polinomial and it means that the data required to store it or to send it is n times smaller than the size of his local circuit where n is the number of polinomial and it turns out that this amount of data is acceptable for practice uh for instance if we are using a 32 beats fielded and the upper Bound for the degree of polinomial is 2 to the^ of 23 the amount of data is about 32 megabytes now since all the partial linear combinations are collected Master

prover execute the regular version of fry with the sum of these linear combinations but this is not the end because we have to prove that this sum is actually linear combination so we have to provide consistency proofs for every random point that was used during the fry protocol but Master prover simply cannot provide this information so he asks for it for other provs and gets corresponding response finally uh we can know that verifier also can can verify this miracle proofs for every respond and in that in that way he

can detect any malicious behavior from the provs so in this way he can introduce some economic incentives or different ways of punishment for uh malicious behavior now let me compare this approach to others so it is well known that distributed snarks can be can be constructed from additive commitments and The Pianist protocol is a great example of it but usually such protocols require public key assumptions fry based snarks uh protocols which based on snarks like the virus system requires to send huge amount of data which whose size is comparable to the size of the

circuit and distributed fry can be can be considered like a balance between these approaches but we can mention that the final proof of the final size for distributed fry protocol would will be a bit larger than the size of the proof of each individual prover here you can see plot uh where we show a number of hashes hash invocations needed to verify every proof it is a good measure to estimate the size of the verification circuit and the orange line is for single proof of one individual prer and a blue line is for concatenation of of M

proves where m is equal to 10 in our case and the green line is is for distributed fry protocol output now let me um let's move on to the second problem which is proven of correctness long run in computation the picture in this case is very similar to the previous one but in this case the input of each prover can depend from the output of another and let's for Simplicity uh circuit the circuit is the same for every step it's easy to see that in that case we simply cannot compute a single linear

combination for all these provs because all these polinomial simply are not available simultaneously and it means that we need to use some kind of recursive mechanism and as a starting point we can consider and IVC VI recursive proof composition so IVC prover produces a proof that the prior St the prior the that all the previous computations were done correctly and that there is a uh sorry IVC Pro produces a proof that step function was computed correctly and that there is a proof that the price step was correct more specifically we

can combine a circuit which represents a step function and a circuit which represents a snark verifier into a single one single recursive circuit and then we can use prover which takes as input the output of the previous step and uh the proof that all the previous computations were done correctly and he launches snark prover and by doing it he attests the correctness of all the computations up to the current step so recursively we have a proof that the entire long running computation is correct and the key aspect of IVC is

that neither the ver IVC verifiers work nor IVC proof size depend depend on the number of steps in this computation but we can see that recursive circuit contains the entire verification algorithm which is a quite a big overhead for practice so so there is a question can we move out some part of this verification algorithm outside of the circuit accumulated at every step and verify just once at the very end and there is a natural idea to move

out the most expensive part of the verification which is proximity test and as you can expect we can try some similar thing we can try to accumulate linear com partial linear combinations and very similar idea is expressed in the paper accumulation without homomorphism which was published recently and transferring this idea to our settings we uh have the following step procedure so let polinomial G be an accumulator which is essentially a partial linear combination for all the polinomial that we encounter it so far and we want to com accumulate a new

bunch of functions F1 to FN in order to do that we we Pro provide linearity proof it means that we produce a new accumulator polinomial commitment to it and a short proof that the new polinomial that commitment corresponds to the function which is close to the linear combination the size of such proof is asymptotically smaller than the size of the proof for proximity test and it means that this technique is efficient but in order to get this proof short we used relaxed guarantee namely we proved that the new function is

closed to the linear combination but it might not be exactly one and also it means that after a certain number of accumulations we have such a big distance it means that the distance between our current accumulator and the very first function grows with the number of uh accumul uh number of steps and it means that at some point the distance is so big that we simply cannot make any meaningful decision uh this is more theoretical problem there are several workarounds for it but it also leads to practical issue it means that the number of random quiries needed to produce linearity

proof depends on the upper bound of maximum number of steps and it turns out that for at least for some practical param set sets of parameters the size of linearity proof is comparable to the size of the proximity test so it simply means that it's not applicable for these practical cases so we have these two issues and I'm going to present new approach that can address both so here's the Oracle batching protocol uh we have a verifier and verifier has an oracle access to n functions F1 to FN Oracle axis is

depicted as rectangular here the prover in addition has polinomial themselves in a plain text and as an output verifier has a new Oracle F new to the polinomial such that its closeness to the read Solomon code means that every initial function fub1 to FN is close to the read Solomon code as well this protocol is heavily inspired by round function of store protocol which was presented at zk7 ZK Summit 11 this year so let me go through this protocol so as you can expect we we are going to we are going to compute linear

L linear combination so the verifier sample and random point and sends it to the prover prover uh computes a linear combination but the key the key difference here is is that we are using two disjoint domains for the read Solomon code DE in De Prime so this uh these domains have the same size and their intersection is empty and the prover computes a vector of evaluations over in U domain D Prime and sends the corresponding Oracle to the verifier then verifier makes an outof the main sample and gets the correspondent respond from the prover which is equal

to the evaluation at this point of uh uh of the linear combination then verifier samples additional T points from the domain D and gets again gets corresponding corresponding values from the initial functions fub1 to FN next verifier computes two pols one is polinomial z which is equal to zero at each evaluation point and polinomial C which is essentially an interpolation of all evaluation points and finally he constructs a new Oracle if new which is actually a quotient which is uh constructed by using Oracle G and New polinomial Q and

z and this protocol is sound it means that if any of initial functions fub1 to FN is far from the read Solon code it means that F new is also far from the rmon code with with high probability and we don't have a distance Decay here it means that we can apply this protocol many times again we can um apply that sham transformation to make this protocol non-interactive and all that means that we can construct a split accumulator scheme from this which we call boil in that case accumulator is represented by two parts short instance part and long witness

part the witness part actually is represented by a single polinomial G which is a linear combination of all the pols from the PRI step and the instance part is represented by several values the first one is is a bit B which is used to represent which domain we are using IF bit B is equal 1 we use domain D Prime if B is equal Z we use domain D then commitment to the polinomial G and two pols q and Z which are derived from the execution of the protocol at the prior step so at every step we are going to accumulate a bunch of new Pol nomials fub1 to FN in order to do that we execute non-interactive version of the

Bing Oracle protocol so we get a proof and updated version of the accumulator namely we have polinomial q Prime Z Prime and G Prime from the execution of the protocol and we change the value of the bit B to the opposite one and finally to get to get the proof that entire long running computation is correct we need to provide proximity proximity proof for the final quo polinomial which can be derived from the final accumulator State the size uh the complexity of this proximity test is higher but again uh because we need to run it just once appro um it has uh it has better

amortized amortized uh cost and the final note using so given this split accumulation scheme we can use any well-known compilers to achieve IVC IVC scheme from this so let me summarize we consider distributed fry protocol which basically makes it possible to compute a single proof for a network of dist of distributed provs and the advantage is that this optimization can extremely easy to implement so here's the link to our blog post where you can find more details on that and later we described boil split accumulator technique so it makes it

possible to construct IVC which is based exclusively on symmetric crypto assumptions and moreover it's uh practically efficient for instance it doesn't require non native arithmetic and uh for instance comparing with uh folding approaches this witness part of the accumulator is just uh much smaller than the size of the whole circuit because it's just a single polinomial that's it thank you for your [Applause] attention anyone questions um uh so in uh non and

homomorphic foldings the issue that we uh make mer lookups in different uh points of evaluation domain and that's why having distance is growing and uh uh in your approach uh uh uh do you make uh lookups uh in different points for different foldings or in the same points uh the the key difference is that we are acquiring points outside of the domain where our Oracle is defined it's the key it's the key difference it what

exactly it it makes it possible to keep the distance constant okay thank you uh thank you for the presentation I do have a kind of a fundamental question so regarding the whole setup um what is the secur assump about your um Collision resistance what are Collision resistance assumptions so you were talking about the uh distribute Prov and there is a master approver so do you assume that all of these are just kind of not looking with each other and their workers on your cluster what's what's the concrete aggregation setup that you're using actually it depends it depends so you you can consider

different different options so in this in this case which which I described I assumed that uh some some prover can cheat and master prover will detected so he can he can detect it before the final proof is produced but but there is another case so actually uh if this there is distributed proof generation we might we might think of all these provs as a single entity so they trust each other I think it's reasonable for some cases so Master Pro is trusted for consistency but not for U so it's like on is it's it's honest but curious or what what's the Assumption about the master approver uh is master allowed to execute different code or do I assume that the

master appr is like honest no no so the output of the master appr is the proof so it has to be verified so we do not trust Master proof in that sense right okay thank you cool anyone else have any questions Could you um Talk a bit about the performance and like proof size and the proving time the maybe you have it had didn't sorry yeah so uh I think um we thought about it and we decided that uh

the number of hash invocations to verify the proof it's a uh it's a good measure to present because uh the actual the actual time complexity of the pr significantly depends on the nature of the computation it depends uh whether we use lookups or not how depends on many things so yeah we we go with this number of hash inv locations to verify yeah thanks last call cool thank you so much