ZK8: Vampire: a new succinct zkSNARK - Michał Zając - Nethermind

Transcript

foreign and he is going to present a new ZK snark that has the smallest communication cost of all updatable ZK snarks so very excited for this talk thank you for being here and take it away so uh as introduced I would like to talk about the vampire and the vampires is the most communication efficient Ezekiel snark with with updateable setup but more I would like to talk um about how ZK snarks are built like

virtually and easy-k snarks we have how they are built what are the building blocks and how choosing particular building blocks affect well various things so so what are the trade-offs what trade-offs are available for us to to have to to have the snark of the properties we desire okay so so vampire um so let me start with this so uh our SDK snark needs only for group elements and two field elements to show um to show that the statement is true and this is regardless the size of the statement so this is really nice

Improvement um over the the past schemes so um to to put you into context for example Planck needs seven group elements and seven field elements and it's like more than so the proof is more than twice as big and then we have Marlin which needs like 13 group elements Sonic which even needs like 20 group elements of course we also have graph 16 as a case nark that needs only two group three group elements but uh well graph 16 has known limitations like it's non-updatable so it means that if you are given a SRS or CRS

then you then you cannot just allow people to to update it to ensure that they feel secure with that particular SRS and SRS that is generated needs to needs to stay and cannot be changed and graph 16 is also non-universal that means that you need to have a separate SRS for for every circuit you want to show on the other hand vampire similarly to Blanc Marlin Sonic is is updatable and Universal that means that you can generate a single SRS and have it for every seal code circuit you like up to some some given given size

okay so how this was possible so um it was possible because of three things so first of all we used r1cs Lite arithmetic representation instead of r1cs and that allowed us to shave like two group elements versus Splunk or even three groups elements versus Marlin we introduced a novel subject argument called count uh what what allowed us to to shave like one group element versus Aurora subject which is for example used for example in Marlin and we also used more efficient way of

batching polynomial commitments Okay so how ZK snarks are built so we have as usual we have prover and verifier and some relation and the prover wants to convince the verifier that um that for some X it knows uh witness W such that they are in the in that this predefined relation So to that end I'm going to present an idealized model which is not very efficient but from this idealized model we know how to you know compile things to to an efficient SDK snark so in um so so to to convince the verifier the approvers and some polynomials some

bunch of polynomials p11x P1 to X then the verifier sends a random challenge that the proverb responds with another set of polynomials and it goes back and forth okay eventually the verifier sends I would say like a special challenge evaluation challenge and the prover responds with evaluations of these polynomials at this and this special challenge then the verifier checks whether some equality on the evaluations of the polynomials hold and and we are done as I mentioned this is idealized model

which is not communication efficient because like for the sole reason that the sending polynomials is really not efficient at all okay so our first step was going from r1cs to r1cs Lite so let me let me introduce r1cs light so similarly to r1cs we have an arithmetic circuit with multiplication and addition Gates uh and this circuit is described in some Matrix w and we have also a vector Z so the vector Z is built out of three sub vectors that L is at R and

um and the vectors at L uh dot ZR which is a pointwise multiplication between z l and ZR and ZL can be interpreted as a vector of left inputs to the uh to to the gates and that are right inputs to the gates and what we want to show is that the wz equals zero is zero and this is very similar to r1cs where we we don't have a single Matrix but we have three um and we have matrices ABC a corresponds to left inputs and B corresponds to

right inputs and C corresponds to to the outputs of multiplication Gates and what we want to have is that a times Z times B times Z minus c times Z equals zero um so we also have vectors that a z B's is that c which are multiplications of a times Z the B times zc times that and eventually what we send in the in this proof are four vectors is a vector Z along with this Vector z a z b z c okay on the other hand in r1cs we have a

single Matrix which is bigger than um and then Matrix in in r1cs and we show like a single that a single multiplication is zero and eventually what we need to to send is only one vector so that allows us to uh to to save the communication of free group elements okay so we had this picture um about how certain arcs are built so actually we can update it and replace this this first message to to a polynomial Z and also evaluation headset

okay so um let me briefly discuss how we go from matrices to polynomials so um we have a matrix W and some Vector Z and we want to have a product of of them to be zero so but you know how how the multiplication of matrices works so we what we require is that we have for all X in some h uh this sum of Y in H of w x y times that y be zero okay I I didn't mention one thing so uh this

Matrix we have we don't enumerate rows and columns by like numbers like one two up to say n but we use some multiple multiplicative subgroup H and elements of that multiplicative subgroup too don't numerate them that's why we have X in in age okay so we can define a polynomial such that for every X this this polynomial takes this value we we need to show with zero we can go even further and introduce polynomials that interpolate elements of the Matrix and elements of

the of the vector and finally doing some mathematical trickery allows us to introduce like a single polynomial that um that well have this property that um we don't need to to to say like what happens for every X in age but we can have like just you know one polynomial okay so the next step is uh is Count our novel uh some check argument so in some trick argument we have two parties prover and verifier and proverb and here I I don't uh I'm not going to

talk about zero knowledge so I I gave them the the same same input namely and approver and verifier knows polynomial X some value V and in the group h mm so H is is a this multiplicative subgroup of size n and what prover tries to to show to the verifier is that if it evaluates the polynomial p on every element of this group and it's sum sum that there are all these evaluations then the result will be V and some trick argument is is basically

a argument for for that to be true and uh one of the most used uh soundtrack arguments is from Aurora uh so before we continue let me introduce polynomial Z which is uh zeroing polynomial I just realized that everybody should probably know what Zeta X is because that was one of the questions required in this submission form for for this conference um and Aurora uses the following fact that if uh if the sum over h of B evaluates to V then there exists polynomials R and Q

such that a p x equals V by is the size of h plus x times RX plus Q X is at X so what actually proverb does in the setup is it sends the the value V Arc RX and QX and then the verifier just checks whether whether this this equation holds so so that allows us to continue with our considerations on polynomials um so so we we're seeing this picture we have this polynomial p

and now we introduce a new polynomial Phi x w so we introduce the second uh we introduced the second variable just to make rid of um so it just to make rid of of some for for a moment but then we also fix the first coefficient okay so we pick some random Alpha and we introduce uh PSI Alpha at Y which which has x equals Alpha and then we we have a nice sum over y c alpha y equals zero so what we actually do we compute R and

Q such that Phi Alpha x equals x times RX plus Q X is at X so we come to this picture where we replace the second the second set of polynomials sent by the prover by uh by the subject argument good so now let me um let me go into to count so before I go to count I would like to say something about kcg commitment scheme which you probably know so so in kcg commitment scheme we need a trusted setup SRS it's a number of group elements g g to the S up to G to the s k

where K is the the biggest degree uh which which a polynomial we commit to it can take and some element H in in the second group so we have our polynomial f and the commitment is just a evaluation of this polynomial at at this secret Point s uh represented as a group element and the Assumption we have now is that it's invisible to compute G to S to n if this n is not in this range from 1 to K okay

I think this is the security assumption that is for most zika snark used and now we have a very simple observation and that if we want to have a polynomial if you want to commit to a polynomial that has non-zero coefficient FM so the coefficient next to X to M then the SRS needs to have G to the s m right because otherwise this this assumption would be broken so uh now into count so we modify a bit our our trust that setup and we introduce a gap

so our tricep setup is now ggs G to the cap minus one g to the Gap plus one up to G to the to Gap so basically the adversary the prover cannot commit to polynomials that has non-zero uh guy Fusion next to x to the Gap and we use the following fact that if f of x is of degree smaller than size of the H then a sum over elements of H is equal to F to at zero times size of the H and we call it V and as mentioned is uh so let's assume

that the degree of f is smaller than than a gap minus one and we introduce another polynomial F Prime X it's it's equal f x times x Gap minus V by h x Gap and it well it doesn't look very nice but let me um let me say a bit more about it so let's um so let's uh let's look at this particular polynomial so um so it starts with X Gap right because we we moved everything by X Gap and then on the first first coefficient we have F0 minus V by h x Gap

so for the prover to be able to commit to such polynomials we need to have this value to to zero each other okay so how it count works so we have prover and verifier the prover now knows the the polynomial the verifier knows only the commitment to the polynomial uh the prover computes this polynomial F Prime and sends commitment to to f Prime now the verifier needs only check that that this F Prime was computed correctly what what is done using billionaire

pairings okay so we had this picture we're using Aurora so now we can shave additional group element additional polynomial by replacing the Aurora some check with with count and more precisely well we as I mentioned this is idealized picture right so we don't actually send polynomials because it's like super inefficient what we really do is we send commitments to polynomials okay so um we we have like one step remaining is the most efficient batching

or maybe it's not the most efficient batching but it's a batching with a different trade-off I would say so let's have evaluation points X from X1 up to x k and some polynomials F from F1 to FM and let's say use dist a to to say like what's the number of distinct elements in in a vector so we have two ways of batching polynomial commitments so first of all for each eye we can batch openings of all polynomials FJ evaluated at x i so uh to put it like more illustratively

we can batch it say we have like the polynomials um F1 F2 F3 uh and we can batch all of the openings that open at some point X1 okay so it doesn't matter which polynomial we are opening it only matters that we open um at the same point so so this needs to send here we need to send like this x openings on the other hand we can do things other way around so for Edge J we can batch openings of all evaluations of FJ and here the thing is that so we have

all these polynomials F1 F2 F3 and we can batch all the openings of F1 all the openings of F2 all the openings of F3 regardless of number of points they are opened at and in this case we need to send like this F openings okay so so this is a straight-off when you need to open your polynomials at multiple points then to then you want to use the second way of batching but if you if you have like multiple polynomials evaluated at the same point then you should be fine with this first way of of batching

okay so currently we are investigating very various variants of of vampire one of them is is a transparent vampire so we ask the question why do we need a SRS in in our SDK snark so actually we have two things that require SRS one is the kcg polynomial commitment scheme but instead we could use some fry based polynomial commitment right like in Starks on the other hand we have count which also relies on on SRS but instead of count we could use Aurora

so we would be worse by by one group element but we could also remove SRS altogether that would give us a transparent vampire so so other variants and trade-offs so so we have this a trusted setup versus trustless so trusted setup allows us for a more efficient verification and shorter proofs but also that um and also that allows us to to use count which also makes the proof shorter and it's uh as a subject it's a more efficient argument on the other hand uh we could use a transparent

um transparent snark which would blow up our proof size to logarithmic but the SRS sorry that would be uh the the proof size would be logarithmic the verification would be also more difficult and we would need to use Aurora we we have also like a third variant where we use trusted setup but instead of count we just use Aurora and that allows us to to have a shortened SRS an SRS which is a bit more MPC friendly and we can utilize existing srs's because when we use count we need an SRS with

this Gap and like most of the SRS issue you see in the space don't have this Gap so um and that concludes my talk if you want to learn more details check check out our paper it's on ePrint and I'm happy to take questions [Applause] ah awesome so we have a mic so if anyone has any questions I'll bring you the mic um any questions oh one question here in the back uh hello I'm Dmitry coverage do you have

any kind of concrete efficiency benchmarks for for your scheme and something like comparable settings yeah we are working on implementation so um the thing is that um I think that the biggest trade-offs we have in this setting come from um sorry let me go back uh is r1cs versus r1cs light so here the the thing is that we we need to to evaluate uh bigger matrices right

because we have this uh blow up from uh n times n to free n times times free n and that um that uh makes the prover a bit a bit less efficient um uh however I will count is more efficient than Aurora because well it's it's like it's a super simple uh some check arguments so um well I don't have any numbers right now but we are working on the implementation uh any other questions from the audience uh okay