zkSummit - Into the deep end: making sense of PLONK - Zac Williamson (CTO, Aztec Protocol)

Transcript

[Music] hi everyone I'm I'm Zack I'm the CTO of the asset protocol we're a previously preserving like we any previously preserving smart contracts on aetherium but I'm here today to talk about a new R&D project that we've been working on a collaboration with Eric Amazon at critical labs plunk and this talk is kind of just I was told to not spare any detail so I'm going this is to talk to kind of get into the guts of plunk how it works like and how you matter how you convert how you you create a sink I'll give it to knowledge at a polynomial

schemes so I think yeah Alessandra gave a very thorough overview of this so I'll just give that very high-level summary they're kind of three failures of snark and I'm kind of including stuck in this world where you have this the non-universal ones where you have circuit specific trustor setups generally they're very efficient in verifier but you have this pot this coordination problem of managing these trust setups and the common reference string Union is quite large they have Universal set of snacks so that's in the vein of sonic monitor and plunk where you only need one trust is set up for arbitrary circuits that you want to create and then you have a per circuit you have this kind of pre-processing step that's transparent and trustless the reference strings that

get produced generally smaller than long universal snacks verifies they're still succinct but the proven verify efficiencies are generally a little bit worse than not new vessel and then finally a transparent but world where you use things like IOP based pulmonary commitment schemes or in order to implement a holographic crew system like Marlin or plonk and you don't have a setup but you suffer with a slightly higher precises so the the new wave of snacks has been kind of coming out over the last few a few months there's been like an enormous amount of innovation a rather snarky summer and so circuit construction for

really takes place in two phases you have this reference string generation that requires a trust to set up and then a circuit specialization face and yet it's kind of summarizing what I said oh yeah so Klunk Klunk is a universal snack where you're it doesn't use our ones CS instead it uses a more simpler era ization where you or circuit is defined using addition and multiplication case the benefits to this is the proof of efficiency and verify efficiency are really quite good the proof sizes are very small but you do pay for your additions they aren't free like the angrel 16 however you can implement very interesting custom gates which can

provide a lot of it quite powerful functionality which I'll go into at the end of this talk we have some benchmarks now the library are pre-construction library it is very new it is only a few weeks old prequel concepts you know health warnings and all of that but we were getting quite good times for both of the proven the verifier specifically for about 1 million gates proof conception time is under 23 seconds and there's quite a lot of low-hanging fruit we can use do to optimize that and that's all using the VM t-54 curve which is the curve that ethereal supports with precompile so yeah woman gets all in pretty good particularly when you can actually do quite um you can create quite expressive gates that perform a lot of work so for

example in the kind of full implementation of plunk boolean constraints are free things like you can do mimsy hash rounds with a single gate and you can do a PowerPoint additions with do gates better shows Valdez or most proofs you can get quite low gate counts so it's good at that kind of stuff is very good of binary decomposition but it's not good when you have - in addition gates when you have these quite long linear relationships and so you get this with spanish-based hash functions in particular I think we things we need matrix addition and multiplication so when it comes to proof sizes all then your proof sizes will be 512 bytes for the BN curve if you want

to use so I'm going to a little bit at the end about service turbo plunk construction that we have that we're building which makes certain arithmetic operations very efficient that will have 128 bytes at you approve size but you can see here's some dummy some example constraint counts both if you're just using addition multiplication gates and if you want to use some more some more advanced constructions that we have and so these concept pretty low so for a bind if you want to do binary composition so you'll need that for you know if you want types integers or things like char t56 peg DB you can straight counters you you only need half the number of gates that you have binary bits you're contaminating rules are free you can evaluate MC hash rounds in a single gate which means 129

bits security level it's about like 50 I believe ok it's fresh so this can get quite quite efficient but you do lose the the generality of our Macias which which means you do have to kind of construct your circuits using some specific primitives so that's kind of what plunk does but what is plunk how does not work how do how does you have in general how do universal smarts work the recipe is pretty straightforward the primitives that we use a pretty pretty pretty simple you want to represent you programmers in a thematic circuit you then want to kind of find a way of describing your circuit using a polynomial identity because you can then use a succinct pull any more commitment scheme like the cat a scheme to commit

to your both the witnesses in your circuit and the kind of a succinct representation of your circuit that would they'll be performed in the pre-processing step and then you can the verify can efficiently evaluate whether you've correctly a satisfied the second description this can be instantiated over any polynomial commitment scheme so the plunk like Marlin is it's completely divorced from the underlying cryptographic primitives that you use to commit to these polynomials you can use like an ip-based scheme like the one that alex on the last stuff in the metal labs guys put out or fractal pairing based with cat a or even groups it on in order the new dark protocol that's come out recently so long in the title this title is technique sounds for

permutation groms bases and then some other website but we use the grant basis to encode our kind of witnesses because they provide a very natural way of representing vectors as polynomials so what we do is if you have like n gates in your second you want to find a multi placate of subgroup which has an order of N or more and so if you're working with prime fields this would be a root of unity so you'll find like an nth root of unity and then you can create a polynomial that represents a vector by taking for each vector elements you multiply that vector value

by a specific Lagrange polynomial and have a blast polynomial is one of the polynomials where when you evaluate at all of the members of the subgroup all of the roots of unity that you have it's going to equal evaluate to zero apart from one of the sub developments so this is this kind of animated gif is trying to show that that basically these are ten Lagrange polynomials where each polynomials only going to be one at one specific evaluation point on the x axis and then you take a linear sum of these to represent your vector the reason why this is useful is because it means that if you have some arithmetic expression you want to if any ways that involves kind of vector elements and vector dot products then you can kind of directly map that into polynomial form where if you have your DS Allah grant space

encoded polynomials then any arithmetic expression involving vector vectors also holds for the polynomials except that instead of checking that some expression is equal to zero you check is equal to zero and what you know the vanishing polynomial of your subgroups so here that that vanishing polynomial will be the lowest degree polynomial that cuts through the x-axis at all when evaluated at all of the subgroup elements so this is a bit of a master's graph but all I was trying to show here is if you have like some if you a of X P of X and C of X include some witness values then if you take a of x times V of X plus C of X C of X then at every single one of these special x coordinates the resulting

polynomial which is going to be this or anything we'll also cut through it also your value back to zero at all of use evaluation points and therefore you know for sure that the vanishing that it will be perfectly divisible by the matching polynomial so that basically all you need to do is check your polynomial expression doesn't have any kind of remainder term this is also been useful because you can use the short super lemma so instead of the verifier evaluating these polynomials and doing complex pollen arithmetic which is going to be expensive if your pollen loss of degree 10,000,000 the verify just used to extract in the valuation of these polynomials at a random evaluation point because if this polynomial A to D holds a random evaluation points it with

overwhelming probability odds at every evaluation point so clonks made up of addition multiplication case and so you want to create some kind of mathematical expression that we can use to test that all the either the gates gates arithmetic has been satisfied and ideally we want one mathematical expression and not not one for additional multiplications because it makes a because you have extra polynomial commitments and it makes things a bit more complicated so this in vector form these are quite simple basically you just create some kind of constant coefficient vectors so these are these are created when you compile in your circuit and what they're doing is they're either they're just they're constant scaling factors on the wires in yours in any gate so you can either turn

send wise to zero you can scale out the constants if you want you can add a constant term in if you need to be one and it's commonly it's in the kind of the plunk arithmetic gate it's a kind of a combined addition of multiplication case where on the bottom left that's kind of thick that the expression you're evaluating where although the queue vectors are defined when you compile your circuit and all the W vectors are witnesses that the prover has to create and then you can in polynomial land you just you can very efficiently convert the use into a Lagrangian base encoded polynomials and then you can test if you have like ten or a hundred million of these gates you can evaluate they've all been satisfied succinctly by testing this one polynomial identity which can

be done very efficiently using a succinct polynomial commitment scheme so that's the easy bit what I've just described is a way of checking that's a very large number of additional multiplication gates have there the arithmetic for each gate has been satisfied but that kind of gets you to this world where basically you've just had a bunch of unconnected uncoordinated gates that you know the input and the output wires like correct but to describe meaningful interesting circuits you need to have some kind of wire consistency check as well you need to check that the Y is feeding into all of these gates correctly map follow what was intended when by the second creator

and specifically that's going to revolve down to checking copy relationships so if you have a splits wire like this you need to check somehow that the Y is feeding into these two gates contain the same value that there has been that the Y value has been correctly copied and this is well where plunk uses a permutation argument in a similar manner to Sonic and apparently Zhang community I believe was originally proposed by Baron growth in 2012 we want to use they're not copy argument to prove that I'll split wise contain the same value and so here's a little example that actually Mary Malec came up with when I was chatting with her about how on earth to describe her mutations imagine you have five wire values where the colors of each square represents the the value

of the wire and the integer is the index of the wire so we want to check that the first the fourth and the fifth wires contain their same value what you can do to do that is you create a plan mutation mapping where you map these these wire values to different indices so you map the first value to the fifth the fourth to the first v to the fourth and then you check that you're permitted blocks they have the same color basically that these the values of these two sets are identical and if they are then you've correctly followed your copy of relationships and therefore you have yeah you you you have a wire consistency check so the way we do this is by using some randomness and basically creating mixing in both the index of your of the

wire and its value into into a single expression with some gated by randomness so we do this for every wire value both for this kind of the original ordering of your wire values which we call the identity permutation and then they're commuted ordering which validates the copy relationships the idea here is that if you take this height user so you take your index you multiply it by random beta then you add in another random elements and your your wire witness value if you do that for the identity permutation the identity ordering the permutation ordering then if you take the product of these two construct constructs they should be identical to

one another and so the one divided every other should be equal to one I have a bit of a working example here to try and explain some of the intuition behind this so imagine the green wires that equal to five to blue want the cyan ones equal to 10 and the blue ones equal to 2 so we have our permutation mapping of we map one two five two maps through itself three maps to itself four maps to one and five minutes to four so what we have here basically again vectors of kind of commuted wire values and the important takeaway thing to take away from this is that each the input vectors the bracket of terms are identical to one another they're just in a different jumbled up order and if you are a malicious prove and you want to

cheat and imagine you have incorrectly follow the permutation so imagine you're the first Y value was not equal to a fifth Y value then you're going to have a mismatch in one of these tones that you're going to have to somehow like account for by mutating an additional Y value in your circuit however you're not able to do that because that's where because the each individual time is multiplied by different random coefficients that's where the be some cameras come in and so the kind of the probability of being able to fake a permutation is basically the same roughly the same probability of finding a collision in a hash function and which is what we want the takeaway from this is well that's like in theory that's how

you do permutation right you you you create this kind of mapping that map's wire values to permitted in is to check your copy relationships and then you perform this kind of Graham product where you take the product of all of your mutated y values and you do the same for your muted Y values according to a permutation and if there's products match you're good and if they don't are they aren't then you you you're cheating however that's something that's quite hard to commit to it's quite hard to create an arithmetic relationship even polynomials that check this because what we really want to do in order to check that that's the case if you have a kind of a polynomial commitment to your grand product terms so for each Lagrange index so for this you're kind of accumulating these these

products together then you then need to somehow check within a you need to compute the product to all of the kind of the Lagrange coefficients of a single polynomial and that's quite hard because effectively it means you need to do a right shift on your vectors before you've concluded that most polynomials we're basically like that then the next element in your vector is equal to the previous one multiplied by this kind of the fractional contributions of that one of you is Y value according to the identity permutation and it's copy permutation and so you need what you basically this boils down to anything a right shift on a on a vector that even could face how do you do that well it's

actually quite simple this was really what started petanque out this was when I was chatting to Ariel a few months ago and I thought this problem was was unsolvable and he was like oh yeah that's easy basically if you have a problem Apollo my coded in this form where it's evaluates to witness values whereas specific subject elements so in this case we have unity then all you need to do is you take the same polynomial and you evaluate it at some random value and another random and then you value it at that same random value multiplied by the generator of that subgroup by the primitive root of unity because what you're doing there is you're basically just accessing the next element in your witness vector which is what you want that's a right basically we have Z

of X then if you take Z of x times Omega Omega is a primitive root of unity then that polynomial is going to be exactly the same as G of X except all the witness value being effectively right shifted and so this is creates quite a quite an efficient permutation argument because you can evaluate this permutation with a single commitment by the true ver this is e polynomial where you check you to basically you that fractional term that we had in the previous slide you you kind of you multiply out by the by the denominator and you get this relationship where you have your kind of your if Z of X kind of represents the

currents your current vector values of your current product then Z of X Omega will represent the this the future values of your ground product argument shifted by one and so you multiply Z vector Omega by the denominator of that fraction of Z of X ability numerator you take the product the difference between the two and if it's equal to zero watching the vanishing polynomial then you know that the polynomial Z of X correctly kind of accumulates these ground product terms that you need to validate your permutation and then the final last thing you need to do to actually check your permutation checkers being satisfied is well because we had this we are computing this kind of fractional relationship of products that needs to be equal to one so what you

need to do is you need to check that your last vector element is 1 I need to take that your first vector element is 1 because it's so that your grant product starts haven't one but here's the thing if you if you validate that your first scram product L if you validate the first element of Z of X as 1 you've also evaluated you've also verified the last element is of these two vectors one because of the previous check because you're you working with the multiplicative subgroup where everything wraps around then Z if Z of X evaluates when you evaluate that at the last sub development then G of X Omega will evaluate will results of the first subgroup element so you're needing these two simple checks to check your copy arguments for a second and that creates

this thing this is this is the quotient polynomial so what this thing is is it's taking the permutation check that you need to perform as well as the arithmetic check you need to evaluate that your gates have been satisfied and you kind of match it all together into one single polynomial commitment by using this these so our here is going to be some random challenge provided by the by the verifier and you just create a random linear combinations of these arithmetic expressions where if if T of X is equal to basically if if all of these mathematic expressions equal or equal to zero munching the matching polynomial

then the same will be the same holds of T of X like will T of X all well that won't have a remainder when when multiplied by the vanishing polynomial and this means that basically the it really it means the proof size for clonk is really quite marginal you have originally initially you have kind of flight commitments of five polynomials here the T of X is Christian polynomial because you're kind of multiplying four terms together and then dividing by the vanishing polynomial its degree is going to be three times higher than the rest so you want to kind of commit to that by splitting it out into three commits polymer commitments the same degree as your original ones so that gives you seven elliptic curve group elements and

then you additionally to two more group elements for the cat a opening proof because you're opening your polynomials at two evaluation points the overall creeper cost therefore is dominated by effectively what is nine times that like the number of duplicates penetrations to be passed up form which is kind of the tradition of the dominant cost for the constructing this proofs is nine times the number of gates which is quite low and it means that quite fast before I continue that was a bit of a lying tour around a rather tricky concept which I always struggle to explain so does anybody have any questions great cool assume everyone everyone everyone cleared up everything then yeah

I mean I'm around after the after if you if you want to chat about it so it's not the end no not by a long shot so here's the thing with plonkers we described it in the paper the a thematic especially evaluating I just addition multiplication gates but there's absolutely no reason why this needs to be the case because effectively what you're doing and plunk is you're performing this pre-processing step where you're creating these selector polynomials that you use to turn off or on arithmetic expressions and there's no reason why you can't include more complex arithmetic expressions in your verification equations because all it's going to cost you if you're if you're clever about it is just additional sector polynomials so you're pre-processing step will be more

time-consuming but that only has to happen once per circuit so it's not like a deal and it doesn't really affect proficiency and it will only marginally effective fi efficiency because the most every selector polynomial you add into your circuit the verify unusable for one additional group exponentiation but still the pairing cost is going to be dominating over the group expansion cost unless you have like an enormous number of sector polynomials so instead of this what about this yeah so what I'm trying to scrape here is a couple of things that you can do for flunk for free without increasing people verify efficiency specifically you can if you want to you can X if you for a given

gate you can access the next gates Y values for free because this is because we are in our proof we are evaluating sorry bit slow so you're about omitting this polynomial Z of X you're barely reaching a two valuation points some random point value chosen by the verifier and that random value multiplied by Omega at the the generator of your multiplicative subgroup and because you can batch together Katty polynomial commitments pull the nipple commitments you can then also evaluate your wire commitments at these two evaluation points and so you can also

perform of right shift on your Y I've had witness values and therefore if you want your on arithmetic relationships for a given gate can evolve the Y values for the next gate and this is incredibly useful for a few reasons specifically it's great for sequential operations if you want to do an addition chain for example where you're concatenated together you're reading together values into a into a sum then if you have access to the next case app wire then the current gates output wire you can treat as an input wire and then add in so and then your left and right ways you can kind of accumulate into your into a sum so effectively for concatenation together values into a sum you don't need if you come on n values you don't need an addition gates you

need n over two addition gates but you can also do some more interesting things so this is kind of what we're implementing right now with our plonk proof of concept so instead of if this is kind of zooming in on the gate where what I have here is kind of almost like a main bus of wire witness values that on the bottom here and so this is for one individual gates and so obviously that as you progress down your circuit these Y values are going to change according to the permutations that you've defined and so what you can do is you can have these individual a thematic expressions for certain bits of discrete functionality that are gated behind selective polynomials which can either be turned on or off at will so you can have things like an extended addition

multiplication gates and by extended I mean it uses the output wire of the next gate if you need it you can do things like boolean satisfiability okay so basically if you want to constrain a wire value to be a bull you can do that for free because you basically you just turn on the selector polynomial for your bull constraint and that can run in kind of parallel to your audition of multiplication gates and then you can get some more interesting things like you can do a mimic hash round gate where you can do an entire round of the mimic cache function with a single gate and then at the more extreme end you can complete you can evaluate elliptic curve point addition on shorts of ours trust curves effectively in a single gate although in practice the the aggregate cost of us is going to be two gates

because this curve gate is going to be consuming the wires that have been kind of allocated to the next gate in your circuit and so that next gate is almost overwhelmingly going to have to be a no other case because you're not going to be able to form any interesting arithmetic relationships in that gate because you've kind of used it's why that is me fixed by the elliptic curve gate but basically you can do point addition into gates which is quite useful and so just to give maybe some examples of how this would work so this is the this will be the the expression for the extended edition gates where it looks exactly the same as the arithmetic expression for the original edition cake it's just that you have this extra term tacked on here in the end you have an extra selected polynomial and then you've got your

commitments to your Abbott wires evaluated at X multiplied by the primitive community which is free to get as so many boolean gates here this is a boolean check for the left wires where you have our sex polynomial and then you just take the left way as you square it subtract out hey you've got a bull for free and then similarly and then things get a bit more complicated with the MEMC gate here but basically because you'll kind of your your front-loading all of your computation into computing these selector polynomials evaluating these gates is going to be cost effective the same as evaluating any other gate in your circuit and this is borne out by tests we implemented the mimic gate in

our proof of concepts and proof construction times increased by less than 10% but the number of constraints you need in your circuit do you spy effective like like five because you only take five gates and finally if anybody's interested this is this is the form you need to evaluate a little point addition so what this is doing is this basically just if you have three let's occur points that's six very at six values you can assign them to one of your six wires and then the expression to check that you're correctly followed the point addition formally if you you can skip out in to meet the normal traditional intermediate terms you need by just inflating the degrees of these polynomials basically um by a factor of

two which is fine because the this won't increase the degree of your quotient polynomial because that degree is already kind of fixed by your permutation argument and this the doogie this is the same degree as you give your permutation argument so effective this this this this would effectively be free but cost about five to ten percent of your previous efficiency so that's kind of it for me that's kind of a bit of a woman sort of plunk how it works what we're trying to do with it and the kind of circuits you can create out of this remarkably efficiently I guess the last thing for me is we're actually at the moment of running a show so set a multi-party computation so you

generate the structure referenced ring you need to construct punk rock Cooper's knowledge I believe it also will map for Marlin over the bretton Eric if I fall curve the old D cash curve and the one that you can efficiently access in etherium through its and free compilers and yeah so if you want to sign up go to our website as tech critical comm they're still slots if people want to take part we'll be running for the entire month and thank you very much so I think I think we actually we have time for like one question in our 50 minutes off but actually it would be great if Ben you want to come set up in the meantime yeah so if there are any questions any more questions thoughts maybe a comment that so I think this

specialization of polynomials to specific sub computations is something I would like to highlight as something very powerful for specific applications it's also not it's something you can easily deploy in pretty much any of the current snark constructions like for example you could go back if you wanted to to be at 16 and specialize the underlying linear PCP for repeated MC computations and say elliptic curves and it's something that a you know if you're reading an academic paper and you say and you don't see any of this stuff going on you know don't don't be afraid you know most likely you can deploy you know very similar ideas I think it's very powerful like again academics don't particularly bother on specific

applications to kind of construct all these gadgets but they can make enormous differences like in practice like if you have a computation that it's all elliptic curve operations and please take your underlying parasitic proof and you know come up with polynomials that are sort of representing those operations directly it's basically a trade-off between software and hardware of the underlying ultimate ization either you have the circular ones yes simulate kind of these gadgets or you kind of come up directly with polynomials that represent these computations I think I think particularly gonna see a lot more of this as we care more about efficiency of particular applications yeah III agree in Charlie I mean if anybody anybody who

knows me I've been talking people's ear off about these custom gates quite a while this because of their power utility particularly holographic proofs systems I think are particularly well-suited to this because you're kind of your arithmetic gates sorry I'm your automatic gates no longer if you take something like a previous ease like loss 16 you're a thematic expressions have to directly reflect the group homomorphism is available to you with in your underlying crypto system so that's one of the reasons why it's limited edition modifications if you wanted to do a more complicated gate like MMC you would need more pairings it would get a little bit more complicated but with holographic proofs or yours committing to multiple areas that no longer is the case and yeah so yeah we'll be seeing more of this I suspect so you mentioned in the

beginning of you mentioned the difference between a universal specific set up and then the moment on your first slide on Shabbat block you mention the chopper block was somewhat more specific it's clear Chapel fog is more specific in the acceptance of more custom gate what do I lose in terms of and if anything in terms of universality you don't lose anything in terms of universality is still this it's still updatable the the reference string doesn't change it's just the pre-prep how you process that reference new string specific and must be compatible with the custom get you're defining or for that matter do customer patient's right yes exactly so it's a transparent process but obviously it's it's more

tailored towards like clunk and polynomial commitments and so it's harder to kind of generalize that to other proving systems that use r1 like well other non holographic sister who's almost yes like or 16 you