ZK Study Club - Plonk with Zac Williamson

Transcript

If you don't mind on the other hand, unfortunately, doesn't know how to to not crash. Um sorry, I'm setting up my Wi-Fi cuz it just crashed on me. Uh it's fine. Okay. So, Adrian, did you start? Uh we are recording and you should see it all in the top left. Oh, yes. Very nice. Cool. Okay, so I think I'll just do the brief intro in case anyone else wants to join in the meantime. Um so, today we're going to be talking about This is the ZK study club, something we we do every once in a while where we get together and talk about a paper or a video or some protocol. And in this case, we're going to talk about Plonk.

And we are very I can't say it any other way. And we're very lucky that today actually Zach, who is one of the co-authors, is going to actually share this with us and present. And we might have some other co-authors join, maybe. Um but yeah, I I want to say like welcome to the study club, Zach. I know I know that uh I heard from sort of our chatter that a lot of people have been reading the paper today or in the last few days. I think we're pretty excited to hear more about it. So, why don't you go ahead? Of course. Well, thanks. I mean, thanks for having me. This is Yeah, I'm looking forward to this. Um so, uh yeah, I apologize in advance if this is just I I This is the first time I've given this presentation, so it might Yeah, uh

we'll we'll see how it goes. Um how do I share my screen? Wait. I still don't know how to use it. Here we go. Uh great. So, I do this. Nice. Hey. Is it working? Yep. Cool. Okay. Can you guys all see that in big? Do you know how to Yep. Yep, looks good. Yes. Cool. So, yeah, um Plonk. Uh permutations over the Lagrange bases for equimetrical non-interactive arguments of knowledge.

Um something we were talking about earlier. Uh so, yeah, Plonk is really ZK-Snark um that um uh only requires one trusted setup to like initialize like the crypto system and then you can convert arbitrary um like programs, arbitrary pre-relations into uh Snark circuits without having to run additional trusted setups. Um, so yeah, uh this is a um first primarily by um Sonic, the Sonic protocol, um and so Plonk is kind of an iteration and refinement of some of the techniques that they were using um with the addition of some Lagrange-based uh shenanigans. So, um I just want to go over like to start with what we wanted to do was explain a bit

of the rationale behind the decisions that led us to Plonk. Um, and so to writing about Plonk and talking about Plonk. Um, basically um if you want to make a universal ZK-Snark circuit uh like proving system, um you need a few fundamental ingredients. Um, you need a way of taking some computer program and representing it by a sequence of like basic um arithmetic gates or logical gates um that can be efficiently um compiled into a zero-knowledge proof. Um, you need a way of succinctly representing a large number of instances of these arithmetic gates because that's where Snarks get their succinctness.

Um, you're basically you're um the verifier is verifying in a a very large number of very simple statements in parallel in parallel kind of. Um, so you you also need some kind of commitment scheme where you agree to succinctly commit to the this kind of representation of an arithmetic circuit and then the verifier needs to be able to very efficiently validate whether these commitments uh actually um uh describe the pre-relation um that um the circuit just describes. So, how do we get there? Um, so I guess just to start with um like most Snarks, um our fundamental arithmetic unit is this kind of the is is an addition and a multiplication gate. Um where our gates are explicitly

fanning two, so you have two input wires, um technically arbitrary numbers of output wires, and the additions and multiplications are all done in the uh finite field um associated in some some finite field um where the precise modulus is given by um is defined by the specific polynomial commitment scheme we use. Um you then want to create some kind of representation of an arithmetic circuit using um relation relationships between the uh like relatively high degree polynomials.

Um the reason for this is because um evaluating polynomials, particularly in the context of elliptic curve cryptography, is very efficient. Um we have commitment schemes where basically uh somebody can uh commit to an encryption of a polynomial um and then a verifier can check this encryption is correct um in constant this constant time. Uh so, the number of um like the amount of computation the verifier has to do is scaled with the degree of these polynomials, which means you can pack more information into them without increasing the verifier complexity.

Um and then that also gives you a very efficient way of evaluating um your Snark circuit because um if you take some polynomial um a collection of polynomials, you evaluate them at random points, if there's some kind of arithmetic relationship between the polynomials, um that's supposed to hold, then uh if it also holds if if that relationship holds for um like the evaluations of that polynomial, um then with overwhelming probability it's also going to hold for the for the polynomial itself.

Naturally, large numbers of terms and conditions apply to that. Um so, anyway, that's kind of the over like the overview of kind of the reasons that we we needed for Plonk. Um Wait. Well, okay. Um and so, the way the way we achieve this is with this Lagrange spaces. We basically effectively include vectors of vectors of variables as polynomials. The idea being if you have some kind of if you have a vector of n elements and you want to include them as a polynomial, you can basically literally just um um pick um predefined x values on your x-axis and then just assign the

y like the y value of your polynomial to be the value of your vector element for like individual x-axis points. So, you can see here this graph is basically the Lagrange these Lagrange polynomials for this the range of integers between 0 and 9 where you can see that each one of these polynomials in sequence is going to be equal to 1 at one specific x value and then 0 at the rest. um This is the the kind of the you can use this to encode encode vectors because basically what we do is you take one of these Lagrange polynomials and the the ith vector element of your vector is going to become the coefficient that you multiply the ith Lagrange polynomial.

um There are a few obviously complications as well because we're working in a finite field and it's particularly efficient to use instead of just picking random arbitrary x points coordinates to use some kind of multiplicative subgroup um whose order equals the size the size of your vector. um Specifically, what we we like this always basically boils down to roots of unity because they're particularly efficient to work with and you can use a lot of fast Fourier transform techniques to compute and manipulate these polynomials.

um Well, basically this is the Lagrange polynomial that we have that I have on the slide. What this is saying is basically, um, if for the for L I of X, if X is the Ith root of unity in the subgroup, then it's going to evaluate to one, and if it's any other root of unity, it'll evaluate to zero. Um, and then you can create linear sums of these Lagrange polynomials to define, um, a polynomial that encodes a vector. Um, and so how this can then be to cons to evaluate arithmetic circuits is because, um, you can effectively take any other arithmetic relationship which holds between your vector elements, and it will also hold betw um, when you when when you perform that those

arithmetic operations on the polynomials um, that you've used to encode your vectors, where effectively the vector arithmetic, if you have some kind of relationship between your vector elements which equals zero, then if you encode your vectors into the Lagrange polynomials, then that arithmetic relationship will hold when you manipulate these polynomials, but instead of it equaling zero, like you you you you will end up with a polynomial which is going to be zero modulo the vanishing polynomial of your of the subgroup. So, um, basically so this ZH, the vanishing polynomial we have, um, it's going to be equal to zero at every single mem- element member of the subgroup. Um, and so what I tried to show in this graph here is the red,

blue and uh, green um, polynomials, they are like three polynomials that represent A, B, and C. So, they've encoded, um, some vectors. Such that if you take the um, the um, dot product of those vectors, um, and then add uh, A and B, and then add C, um, the result should be equal to zero. And so you can see here that result in polynomial form is going to be that orange function F4, and you'll notice that, um, it passes through zero at the all of the X values between zero and nine, because that's the um, yeah, this this is using roots of unity here, which this is just kind of a bit of a toy example. You see that's the general principle.

Zack, can I just I just want to cut in for 1 second just to tell cuz I don't know if you guys keep hearing that doorbell. It's basically anyone who's dropping off over and over again, maybe just stay off and we'll share a video of this just cuz we're hearing that each time you join. Just so you know, keep going. Sorry Zack. Um So I can meet my my machine but then you then if anybody else has any questions or what people here. So by the way, every like everyone feel free to interrupt and ask questions like if there's something you don't understand, it's please like ask about it.

I suspect I suspect you won't be alone. Um so So basically yes, you take vectors you encode them into by using round bases into polynomials and then any after the relationship which held on the vectors will also hold for the polynomials modulo vanishing polynomial. And this is kind of the essence of what makes Plonk so efficient because if we consider the degrees of all these polynomials we're working with, these A's, B's, C's, they equal to the number of the degrees equal to the number of elements in your vector, well, minus one.

Um And so um you you do you don't have any kind of overheads or bloating factors from this representation. So effectively in a SNARK form, the degrees of these polynomials is going to be equal to the number of arithmetic gates that you have and no larger which is rather useful. So now that we have a way of encoding vectors as polynomials, we need a way of actually describing an arithmetic circuit. And so um but now we can actually start talking about vectors instead of polynomials because we have an abstraction here which will allow us to convert vectors to polynomials which makes kind of circuit arithmetic association a little bit easier to understand conceptually.

Um the idea is we have these addition and multiplication gates that we need to construct a circuit out of. And so we can represent the wire values going into these gates as in your WL, WR, WO, and then you can also define vectors of these wire values. Um and similarly, if you want to kind of create addition and multiplication gates via um like basic vector operations, so you know, dot products, additions, um you um you can do it with this concept of like selector vectors. So you can see here on the left-hand side when we just got the multiplication gate, we have these gate constants, QM, QO, QC for multiplication, output, and constant.

The idea is um the multiplication selector will multiply the the left and the right wires by some constant factor. Um similarly, you can also scale the output wire, and you can add in a constant. Um this allows you to like create relatively expressive um like describe relatively expressive situations. If you need to scale some of the wires by constant, you can do so. You want to send some of the wires to zero, you can do so. Um similarly, you can do the same with addition gates, where instead we now have these gate constants, you know, QL for the left wire, QR for the right wire, and then similarly, we have QO and QC for the output wires and the constant. And you can define an addition gate in the same way.

But the interesting thing here is, well, we we we we don't really want to separate arithmetic expressions for our addition and multiplication gates because when compiling them into a zero-knowledge proof, you then needs to um you have you need to have separate equations um so to verify your addition um constraints and your your multiplication constraints. And then you need some way of mapping between the two. Um so like which um which wires from the multiplication are like um connected to the addition gates. Um and that's difficult to do. Um just for a bit of context, this is something that, for example, Groth16 SNARKs didn't have to deal with because what Groth did was um specifically construct the common reference string, like the trusted setup

reference string, um in such a manner that the only way you can construct satisfying proofs is if you like the relative linear relationships between the Y values are satisfied. Effectively, addition is free in Groth16, or close to free. But you can't really get that in universal snark because you can't manipulate your your your setup process to suit the like the arithmetic needs of one specific circuit like you can in Groth. So you need to deal with addition multiplication and find some way of like elegantly doing this without massive increase in the degrees of all of these polynomials you're committing to.

So something that we we noticed relatively early on was basically, well, this we have these selector vectors and they can be zero. So why not just combine addition and multiplication gates into one arithmetic gate. Specifically, just take the two gates we had previously and smash the the equations together and you have one relatively large equation between these vectors which just can can either describe an addition gate or multiplication gate depending on like which which of these gate constants you zero out. So for obviously to give an example, if you want if a specific addition gate wants to in this specific gate used for addition gate, then QM

will be zero for that specific gate and if you want it to be a multiplication gate then you'd send QL and QR to zero. So this gives us a really relatively compact representation of an arithmetic circuit in Lagrange basis form. You have polynomial you can take your vectors of Y values and use Lagrange basis to turn them into polynomials. And similarly, you can do the the same for your your gate constants. And then you get some circuit specific polynomials. So these Q polynomials are going to define one specific arithmetic circuit.

And again, like that that equation that we had over the vectors on the left-hand side, you can turn that into an equation between polynomials on the right-hand side pretty much directly, which is rather convenient. And you can notice also here that the kind of the degrees of the polynomials that we're committing to um don't don't blow up too much. So, you can see that what you have one term here where we're multiplying three polynomials together, um which means that the right-hand side of this equation is going to be um So, if we're in that arithmetic case, the right-hand side is going to be a degree three in polynomial.

Um and so, I'm using here as a kind of shorthand saying, "Oh, this relationship is zero modulo the vanishing polynomial." Well, when it comes to actually checking that in the zero-knowledge proof, you need to you need to prove that, which means you need to compute the the quotient polynomial, basically the polynomial that you multiply the zero polynomial the vanishing polynomial by um for this relationship to hold, and you prove that there is no remainder term. Um and so, that quotient polynomial, its degree right now will be uh 2n because everything because you're dividing it by the vanishing polynomial, which is degree n. So, basically, you can see the degrees of your polynomials aren't increasing very much, um which is good uh cuz that Did they Is Is this different from like did the Sonics in Sonic do they not

do this? So, in Sonic, they their arithmetic addition is somewhat different, um where instead of using Lagrange bases, um they encode um like wire values for their multiplication gates as the coefficients of a Laurent polynomial. So, basically, you have powers of x uh effectively. Um and so, like each unique power of x will be associated with some kind of wire value. Um and so, the one of I mean, one of the one of the upsides of that is it means that these polynomials are relatively nice to manipulate and work with because you're not having to do this rather odd Lagrange interpolation thing.

Uh but, it does it does quite significantly increase the degree of your polynomials because you don't have a nice a relatively like compact way of testing um like an a relationship between the polynomials. What you do in Sonic is effectively, if you if your arithmetic relationship holds, then you have a polynomial relationship where the uh the constant time of that polynomial should be zero. Um but to get that, you then need basically you need to extend your polynomials into negative powers of X, so that to start with the constant gives you a bit of a like a degree of like those are the degree of a factor of two.

Okay. Um Does anyone else have any questions up to now? Just going to throw it out there. Uh I have a question. Sure. Uh so but basically the same thing that that I've asked you on Telegram, like these uh multiplicative subgroups, like how do you derive them? So Because you need them to be like the exact size of your input string input vector, right? So, if if you make if you make a a too big subgroup, then you have a lot of computa- a lot of extra computation to do, which you don't want to do.

Correct. Um that is true. So, it is effectively you need it is a slight um you when you when you assuming that you that this this this kind of this kind of pairing system we have is that you do the pairing friendly elliptic curve, um you want the number of points on that curve to be the order of the of the curve group to be a um a a value that's um has a large number of these roots of unity, but obviously you're you're not going to be you're not going to have a one-size-fits-all solution. So, the standard technique is what the Zcash team done did, um and it's quite it seems to be quite like a canonical way of deriving these curves, is you find a group order a a curve order where um a

large number of powers of two Um are like entries of unity. So, you can say like uh like two to the from two two to I from I equals zero to say like 28 or 30. Um you will have that like that will be a primitive root of unity. You will be able to find the two to the nth root of unity in that. Um and so, that then means that you effectively have to add dummy constraints into your circuit until the number of constraints you have equals one of those nice powers of two. And so, there is an inefficiency factor.

Okay. Um to give an example, I believe this the Zcash team worked extremely hard when they for the Snark release to ensure that their circuits were efficient enough that they could buy basically like like um like the number of constraints was like just just beneath a power of two. Um and uh it gave it gave them like a massive speed up. Um Um did that did that help or Uh yeah, that pretty much answered it. Thanks.

Good. Awesome. Um So, yeah. Before Before any any any other questions? I guess keep going. Cool. Right. So, I think I think we've kind of got to the end of the the Plonky nation. Um so, it's probably worth taking stock of where we are right now because we do not have a Snark. What we have is a way of very very efficiently validating um that the kind of the inputs and outputs of of of a vector of a of a list of arithmetic gates um are sat- are satisfied. So, they can basically make the um the inputs to your addition gates match the outputs, your inputs to your

multiplication gates match the outputs. But, what you don't have is at the moment anyway of um connecting these wires together, um which is a little bit of a problem because that's you you don't have an arithmetic circuit without that. What I've tried to describe in this these two diagrams is the bottom picture is kind of where we are right now, where every single gate is isolated. Its wires aren't connected to any other wires. You you can't derive any meaningful information um like any meaningful relationship between like what do these gates These gates don't feed into anything. They're not connected. And what we really want is a situation like the the picture on the right where um I'm trying to kind of just visualize the fact that actually like the the relationships like the mappings between all the wires in an arithmetic circuit are not going to be uh

nice and linear. You're not going to have like a layer of gates um which then where the outputs feed into the next layer of gates and on and on they go. Um these wires are going to be routed all over the place and um connected to all sorts of different gates from all over the whole circuit. And you need a way of representing that. You need a way of verifying that this is like if somebody's claiming to have said a satisfying proof for your circuit, you need a way of checking that they've actually connected up their wires correctly. Um this is the the kind of sticking point for all universal snarks um because you can't um like like in Groth, you can't really um like add in structure into your reference string, which kind of forces these these what these wire routing relationships to be satisfied. You have

to check it somehow. Um so I just want to kind of just to try and disambiguate what I'm talking about when I'm talking about connecting wires. If we have this example here, this very um simple example of you know one gate feeding into like where the output wire feeds into the left wire of the second gate. That's a connection. So you have like So you have two gates, gate one and gate two, and there is an output wire for gate one and there is a left input wire for gate two. It looks like they're the same in this in this diagram, but they really aren't um and you need a way of um proving that the values on those wires um are identical. Uh if you for for this toy little circuit.

So what we really need is a way of describing the circuit's copying relationships. Basically, which wire values Yeah, for for a given program that's converted into arithmetic form, you're going to have a list of Y values that need to be the same as one another. Um and if they aren't, then um you haven't got a correct set. You haven't You haven't um got a correct um proof that you've done the program correctly because you're not connecting your wires up. So, to try and kind of capture this, um I like to try and I I I like to think of the of like basically consider all of the wires in your circuit and and in one giant vector. So, where here I've basically I've connected I've listed all the left wires and all the right wires and all the output wires.

Um and these are all going to be um unique wires, but they won't have unique wire values, if that makes any sense. Um we want to be able we want to be able we want to check whether um the various indices of this wire vector um contain copies of other indices. And specifically, what we really wanted to actually do is create um two polynomials where the roots of these polynomials um are identical if and only if the wire copy relationship is satisfied. Um this is a little bit abstract, but this is something that we can actually test for in a zero knowledge proof quite efficiently. And um Lord knows we can't check the like uh we we we're not working with vectors. The vectors are kind of an abstraction. So,

we can't really um we don't want to basically we don't basically the the absolute last thing you want to do is iterate through your circuit constraint by constraint um and have some element like validate that um that the wires have been connected correctly because that's uh you wouldn't have succinct you wouldn't be succinct. The verifier um its running time would be rather large, and that's what you have with this kind of helped Sonic idea. So, we can solve this with a with with one of these dreaded permutation arguments. Um and I'm I'm going to try and kind of uh capture the rationale behind it, where basically if you have your vector of wires, you can also create a vector which kind of just describes the wire indices. So, you know, from 1 to 3n uh cuz you know, you have n gates and n wires,

um you can map wire value to like it to a unique index. Then you can also define a permutation function where this function will map a wire index to a copy index. And by that I mean if say for example the first and the third and the fifth wires are supposed to be identical in your circuit then you can say that the permutation function will map index one to three, it will map index three to five, it will map index five to one. The idea is what you're trying to say is like W like the index at one like the value at one should be equal to the value at three which should be equal to the value at five which should also be equal to value at one again. And obviously this one can only if you if you can prove that then you've got your

correct correct copy relationship and so you know your your wires have been like connected to the various gates correctly. And so just to for further clarification if a copy cycle needs to be closed to define copy relationship. So basically it's got to loop back in on itself. So so like the last copy permutation is got like for for a set of wires that are supposed to be the same the copy permutations have to iterate through one another such that like each sigma the permutation function on each index will map to a different index. Um So to give an example here you can see at the very end here we have in our toy example like sigma five maps back to one.

So it kind of closes that loop. And obviously if you have a wire index that isn't copied anywhere in the circuit so it's a genuinely then the permutation function will just map to itself. Why are we doing all this? Well, the idea is we can then create a vector that maps these indices like the your your vector indices to the copy counterparts. So you can basically just list um the So basically what this vector is doing basically saying okay for apply this permutation function to each index in sequence and then there's list of results in this vector.

Um the the reason why this is useful is because this is one way that you can perform a permutation check. So, what I have in this box here on the right is um two um uh uh field elements um where basically I'm just saying that take the product of take the wire index combine it with the one of these permutation vectors multiply the permutation vector by some randomness uh some randomness and and then um do that for every single constraint and multiply them together.

Why is this useful? Um it's useful because if Z1 equals Z2, you you you you've got a satisfying um permutation argument. I'm going to try and explain why on earth that is now. Um it basically relies on this thing the Schwartz-Zippel lemma that effectively if you have some kind of polynomial identity that holds um at a random evaluation point for your polynomials, then with overwhelming probability it's going to hold for all your evaluation points. Basically, the if you have if you if you have um two polynomials, you evaluate them at a random point, and the point evaluations are the same then with overwhelming probability um these polynomials, they share the same coefficients and they share the same roots. Um again, obviously terms and conditions apply here. Um

the like the um the degree of the polynomial needs to be significantly significantly smaller than the um the uh characteristic of the prime field that you're kind of working in. For us, that's the case. Um like these polynomials, the degree is never going to go beyond a few million or maybe 100 million, but the um the um the characteristic of the field is going to be like 2 to the 250 or something. Um basically, if you look at the top the top right is where I have these these Z1 and Z2 relationships, um but you can use a Schwartz-Zippel lemma because basically those betas and gammas, they're random, right? So, they're effectively you're you can also say that you're effectively evaluating a polynomial at a random point gamma. So, here I've I've written Z1 and Z2 as

polynomials in X where you then convert X into gamma, and if Z1 equals Z2, then these polynomials, with overwhelming probability, are going to be equal to one another as well. Um and so what you can tell from that is if this is the case, then the roots of these polynomials are going to be the same. Um obviously, they're going to be like in different orders kind of if you list the roots. Like each product term in P1 of X is going to be equal to one of the product terms in P2 of X, but just in a different order. Um uh and uh so, what what do you get from that?

Well, okay. Now, let's zoom in and think about the case where you have two um matching roots to these polynomials. So, you know the roots are the same, so let's pick um a root from P1 of X and a root from P2 of X that equal each other. And you have this relationship WI plus I beta equals WJ plus the permutation function on J times beta. So, I and J are basically um two indices of um the the vectors um uh the Y vectors that we were using before. Beta, though, is also random. So, again, we can then lean on the short simple lemma again. In the same way that we replaced gamma with um say, "Okay, gamma is a random variable, so you can then basically replace it with

um an indeterminate value and say this is now a polynomial, and these polynomials hold." You can do the same beta. Um which means that you have two degree one polynomials, WI plus um IX equals WJ plus the permutation function on J times X. And again, if these polynomials are equal to one another, so are their coefficients, which means that um WI equals WJ when the permutation function on J equals I. Um and so, that that permutation function was defining the copy relationships, right? So, in our first example, we were saying Y if Y is 1 3 and 5 are the same, then the permutation function will map 1 to 3, which means W1 will equal W3 if this

permutation check holds. And similarly, it'll map 3 to 5, and so W3 has to equal W5 if this permutation check holds. And similarly, 5 maps to 1. And so, you can repeat that for the your entire circuit, basically. You define all of the copy relationships. And you create that permutation you create a vector out of that permutation function. Um and then you use that um in this kind of grand product argument. So, you compute these values Z1 and Z2. And if they are the same, then with overwhelming probability, um your um permutation has been satisfied, which means that you then know that the the relevant like all of the Y values um in proof that's being presented to you, um they satisfy the the copy relationships

of that specific arithmetic circuit. Does anybody have any questions? Because I have to admit I've never successfully explained the permutation check to to anybody ever. Uh yeah. Yeah. Hello. Um yeah, I have a question. It is very elegant. So, um is Sonic also using some similar like permutation uh checks? Yes. So, what I should have added at the very start um was a massive attribution to Sonic because uh Sonic um pioneered the use of a permutation check um to to create a succinct SNARK.

Um so, this a lot of these techniques were taken from the Sonic paper. Um Sonic used their permutation check in a slightly different way. So, where we're permuting where basically using this permutation check to check copy relationships on the Y values, what Sonic is doing is they're effectively using a permutation check to well, the permutation check really for them it targets the uh so, if you go back to the earlier in my talk by me um we have these polynomial these key polynomials which defines these kind of constant coefficients for the gates. Um and Sonic was using uses the permutation check to basically ensure the prover has correctly constructed these um constant coefficients correctly. Um so, it's it's a it it applies it in a very

different way, um but the the mechanism and techniques are still the same. Okay. And and the the degree of the polynomial here is three and three times n, right? Yes. And the polynomial the degree of the polynomial using Sonic uh is it also like three n or something? So, it's about three and I'm I must commit I'm I'm convinced I'm on shaky ground talking about Sonic's permutation like the the degrees of all these polynomials. I think the the Sonic permutation increases the degrees by three um and you start with Laurent polynomials.

So, they're they're they're Okay. Um and then, you also One thing we were really focusing on Plonk was um basically reducing the number of permutation steps cuz these things are expensive. Um and so, we only have two um for the entire circuit. Uh and that was one of the one of the key kind of innovations um that we were that we were targeting was to kind of really reduce these number of permutation checks down to an absolute minimum. Okay. Very cool. Thank you. Cool. I guess I'll I'll carry on cuz there is there is a massive elephant in the room that I haven't talked about, which is um the these product terms. How do you compute them when you're working with

Lagrange bases? Because Okay. So, I was we had this abstraction where I was talking about this vector of all the Y values, but we don't have that. We have polynomials which encode which represent vectors for um left wires, right wires, and output wires. But that's no bother. Um that's easy to fix because basically we take that permutation vector we had from before and we split that down into three ones three components as well. So we have that identity permutation which was just like this literally just a list of integers increasing in value. You can split that down into three different polynomials and similarly you can do the same with your your copy permutation vector. And then you have at the bottom here written out basically the how do you actually compute that product

term? Because if you now if you now if you take these three polynomials um the square at the bottom. The Lagrange coefficients of these polynomials are going to be the same as the coefficients as the as the the product terms that you're multiplying together in Z1 and Z2. So great. That's that's useful but now okay fine. So now you have if you have if you have that if you compute these polynomials each Lagrange you need to now compute the product of each Lagrange coefficient to get the grand product.

And so this is a bit of a misnomer here. By the Lagrange coefficient I mean like the thing you're multiplying the Lagrange polynomials by. It's like technically they're not polynomial coefficients so I'm I'm just calling them Lagrange coefficients. To do a grand product argument you basically again um highly highly similar to Sonic. You effectively have a very simple stock circuit again to do a grand product argument. You basically have a long sequence of multiplication gates where the outputs are feeding into the inputs of the next multiplication gate. And so what I tried to write out here is basically this is like the the right wires are going to be the Lagrange coefficients for that those polynomial terms I mentioned before. So here we're working

with computing the grand product for the identity permutation. So here's the problem, right? Um uh writing out these Lagrange coefficients and indexing individually we have this kind of this giant large product term at the bottom where for the ice um Lagrange polynomial like the ice Lagrange coefficient we take a product of all these wires in the permutation um value coefficients. Then you multiply them by some Z Z value um in a in a in a vector of Z values and if that's equal to the next Z value in the vector um then you have this then that also that describes this kind of this um this this multiplication ladder thing um cuz

you're saying basically there that the output if Z represents output wires um then the output wire uh the the output wire uh sorry if Z um like I represents output wires and Z sorry if ZI represents left wires um and ZI + 1 represents upper wires then you can say that basically like the circuit's left wires if you take the vector of the circuit's left wires that's exactly the same as the vector of the circuit's right output wires um but right shifted by one.

Um and and here's a problem right because I've been talking about vectors but we're working with polynomials and whilst you can conceptually it's relatively easy to do a right shift on a vector how in the blazes do you perform a right shift on a polynomial's Lagrange basis coefficients? Um it's a bit of a a bit of a difficult problem and this was really one of the kind of the inciting incidents which led us to develop Plonk was realizing that you can actually do this. Um specifically um the fact that we're using multiplicative subgroups um is one of the key reasons why you can why why you can perform this kind of weird right shift thing because if you consider like a multiplicative subgroup of order n + 1 because um the size of these vectors is going to

increase by one so you need to increase the order of your subgroup by one um and we have a generator omega of the subgroup and so this is going to be like practically when implemented this is going to be the n plus one roots of unity in whatever prime field you're working with. Um and omega will be the primitive root of unity. So, the i of the graph polynomial is going to be this weird product term where basically you're taking the product of x minus the primitive root to power j, um and dividing it by like the the the roots you that's associated with this the the i of the graph polynomial, the i root, um minus the um omega to the j. What this is basically doing is in this product term, uh if x is any of the roots of unity that isn't omega to

the i, then there's going to be one of the numerator terms will be zero, which means the graph polynomial will be zero. Um and if x is w omega to the i, then the numerator will equal the denominator. So, you it's going to be equal to one. Again, you just have this big this is a delta function where if you evaluate l i at omega to the i, it's one. If you evaluate l i at any of the other roots of unity, it'll be zero. So, here's the thing. What happens if we reconsider take this Lagrange polynomial, but instead of evaluating at some indeterminate x, we evaluate it at indeterminate x divided by the primitive root?

Um if you do this, then if you consider the product term, well, x is now divided by primitive root. So, you can you can factor that out. Um you can basically you can take in the um in the numerator that omega to the j term, you just um multiply that by uh omega, and then you can factor out um the term omega to the minus one. Uh but then if you do that, then you also you can then include that in the denominator by just increasing the degrees of all of your roots by one. And so, if you do that, well, consider what happens in this product term when j equals n plus one, then the numerator you'll have the primitive roots x minus

primitive roots to the uh n plus two. But this is a this is is multiplicative uh subgroup cyclic, right? So, omega to the uh n + 2 is equal to omega. So, this thing cycles around, basically. Um what you have is that product term, you've effectively shifted all of your omegas up um uh you you multiply them all by the primitive root. Um and so, if you consider the term in this in this product that you're skipping, before you were skipping the ith root of unity, but now you're skipping the ith root of one root of unity. Um because effectively you've just multiplied up all your roots by uh the primitive root. Which means that the ith root of one polynomial when evaluated at x divided by the primitive root is the same as the i + 1 Lagrange

polynomial evaluated at x. Which means that if you take some if you commit to some polynomial some Lagrange base polynomial and you evaluate it at two points, you evaluate it at some you know some z and then some and also some some z divided by the primitive root, then your second evaluation, like the Lagrange coefficients of that polynomial will be the same as the first, but they've all been they've all been shifted by uh to the right by one. Um and so, that gives you your right shift. That gets you So, if you go back a slide, that So, in that that long product equation um on the end of the left-hand side where you have um z the ith index of z z and you wanted to subtract the ith index the i + 1 thing index of z, well, now you can just commit to one z

polynomial and evaluate it at two points where um the second point is just the first divided by the primitive root of unity. Um and that's how you get your That's how you can get That's how you get That's how you can compute a grand polynomial. And so, this is the permutation argument um stitched together into something which is uh attempting to be a coherent whole. Um so, yes um I was I was told to not to not keep it too high-level because it's quite a technical crowd. So, yeah, here's some math. Um basically um the what we have here um at the um the this kind of first rank of boxes you have the identity permutation like that that vector encoded as a rush

polynomial and again because you're just listing vector elements that's very simple this is I multiplied by the rush polynomial. You then have the three permutation polynomials. You can actually skip out the other two the sec the second and third identity polynomials because they're basically just equal to n plus the first identity polynomial and two n plus the second the second the third identity polynomial is equal to the first plus two n and the second is equal to the first plus n. And so what you can do is you can now there's there's there's the Z1 and Z2 vectors we were talking about before.

You can encode them also as polynomials where effectively this is the this is your grand product where you're iterating over all of your constraints and at each layer you're basically computing this grand product which where the number of terms in that product is going to be increasing by one up until you hit n. And you do you do that with the Z1 and Z2 for the identity permutation and the copy permutation respectively. And then you have these four polynomial relationships which if they hold mean you have a satisfying permutation argument. You can see here in the the first the first relationship we have looks it's it's exactly the same as if I go back two slides this so this this product relationship for one single

round of like coefficients this is now that encoded. Hang on. Encoded in polynomial form where because these are not vectors anymore this thing isn't equal to zero but it's equal to zero modulo the vanishing polynomial. Again with one extra caveat which is now our vanishing polynomial the order of our subgroup is now one greater than the number of constraints we have because for the grand product argument to work you need you need one extra element to the subgroup to cycle around. So our vanishing polynomial is now like the old the polynomial but you're just dividing out that that last term that you don't care about.

Um And so similarly, you have the same relationship for all your permutation copy permutation, and that should be equal to zero modulo vanishing polynomial. And if those two equations are satisfied, then Z1 and Z2 represent ground product the the ground product arguments for your permutation checks. And then the only thing to do is you need to check two things. One, that the first coefficient of both of these ground products is the same, so they have the same starting point. So we go back to that circuit diagram. And so here that, you know, it starts out with left YB equal to one. Uh technically, it doesn't have to be equal to one. It just needs It's just that the both ground product arguments need to start at the same point. So that's what you're checking with the third argument here. Um and then the fourth the fourth polynomial evaluation,

um you're now checking that those ground the ground product terms for your identity permutation and the copy permutation are both equal to one another. Um so you're taking what would have been the nth first coefficient of your ground product polynomials, um but you shift it down by one um by evaluating at X to the power of omega. Um so you can then use the nth Lagrange polynomial to to kind of select it out. Um This is also necessary because your vanishing polynomial now doesn't have that that that last nth perform term in it, so you can't um you can't like select out the nth perform term and make some any kind of um uh

like arguments about what it what it what what that relationship should be because your um vanishing polynomial isn't correctly formed. Right. Okay, so this is the the last slide. Um so sorry, I I know this has been a bit of a um Yeah uh but that permutation argument was Well, I've done my best to explain it. Hopefully hopefully uh it wasn't uh No, it's been super helpful. I think I'll have to like read the slides again. If you could send the slides, that'd be great, but very helpful. Um and so finally, if you want to put it all together at least in polynomial form, uh you have five verification equations, right? There's four that we had for the presentation, and then that one equation for the arithmetic organization.

And I've been saying everything is zero modulo the vanishing polynomial, yada yada yada, but you actually need to prove this. This means you need to compute what that quotient polynomial is going to be, what do you multiply the vanishing polynomial by uh to for for for this relationship to hold. And so that's this T of X polynomial, where effectively you can um you can roll all these equations into one by just taking some random R, um and um like multiplying each verification equation by some linearly independent bit of randomness. Um What this all means, putting it all together, is basically if you want to construct one of these proofs of knowledge for a circuit, you need to compute um the polynomial the coefficients of uh six polynomials, three for the Y values, two for the

grand products, and then this this T of X um quotient polynomial, where the degree of the quotient polynomial will be uh 3n um because uh like the numerator's degree 4n and the denominator's degree n. Um Additionally, if you're wanting to use Kate uh polynomial commitments, you need to we're about now evaluating these committed polynomials at two points, so you need two group elements for your um opening proofs, um which encode um a degree n and a degree 3n polynomial respectively, um because uh you're opening T of X on one of them.

Um and so the overall cost for the prover, if you kind of ignore the the the fast Fourier transforms, which yeah, I mean obviously for really large circuits, that's not that's not uh appropriate, but like generally like the the the dominating cost of these thing of of constructing proofs is going to be the elliptic curve scalar multiplications. You need 12 of them for each constraint that you have, which means 12 times the number of arithmetic gates, which um depending on your circuit structure can be extremely efficient. Obviously, comparing something like a Groth circuit, where addition gates are free, if you optimize your circuit under that assumption, then you then turn it into Plonk, it's going to give you It's not going to give you a great result.

But um I mean, again, maybe some people in the chat can kind of can have more experience with this than I do, but I'm just doing basically running through some basic examples of the common algorithms that you uh tend to SNARK-ify. I was getting basically like between two to three times the number of addition gates for for multiplication gate. Um which means that generally this is pretty pretty efficient. It's kind of like between four and five, three to five times slower than a Groth16 proof. But, compared to Sonic Sonic, it's it's it's the the degrees of your polynomial are quite a lot less, so it should be quite a bit faster.

Do you think the compilation tools could be tweaked to not cost addition gates as zero? And how much would that change? This is something Well, this is something I'm very intensely focused on at the moment. And quite a few people that are the Aztec, which is basically um writing some of these uh compilation tools kind of from scratch, because we want to create like What we're trying to do is create quite a nice like a clear abstraction layer between a SNARK program and the actual zero-knowledge proof of constant degree.

So, that you can focus on writing reasonably nice high-level smart language as well having to then also like wire them into a proving system. Uh so, basically we're creating a kind of a virtual machine environment with some very low-level um opcodes to kind of assemble both the constraints of your SNARK, so those few few few vectors, um and also the actual wire values for a SNARK proof. Um and then the idea is then you can take a high-level language and compile it down directly. uh so this so this little you little primitives um anyway, so you're basically um uh I'm sure existing tools can be adapted um and I'm very excited about that and and we're also trying to do do a few things

from the ground up um because just because of the relatively unique arithmetic structure of Plonk. Are there any other questions? Uh I think there was typo in the last slide like Yeah probably. Uh in the chat, like the last one should be ln of x, right? Uh you're absolutely right. Yes, it should be. And also those z should be evaluated at x divided by omega. Um yeah. Yeah. Yeah. Uh x is coming up.

Okay, Zach. Uh I have another question. Um Uh because I I I I want you to know if your techniques could improve the current, for example, uh confidential transaction implementation. The current I didn't quite catch that. Uh for confidential transactions Ah. Basically, uh there you don't I I guess we don't need like multi-multiplication uh gates. We only need to have addition gates involved.

So, if you use the same tricks or same like techniques you used in Plonk, do you think that's we could improve uh for example, range proofs, uh this kind of stuff? Interesting. So, it depends what you're after. If you're after relatively basic confidential transactions, so where you're not you're just you're as you say, you're just you're just doing additions uh confidentially, then um well, the reason I actually got into all of this is because uh my original zero knowledge zero knowledge proofs I wrote were exactly to do this. Um so, that's what the assets stands for, anonymous zero knowledge transactions and efficient communication. Uh, basically it's um, you can use this the Plonk

structure reference string to create very explicit range proofs that are very efficient. Um, uh, to give an example, like you can um, like uh, we compile uh, like a joint script sigma protocol for confidential transactions down into um, a proof which literally takes milliseconds to both construct and verify cuz um, you need um, it's like like a handful of elliptic curve scalar multiplications. So if you're doing very if you're doing very um, like algebraic and simple things like that, there's a good chance that um, like um, avoiding the Snark abstraction and just going with sigma protocols will will give you that speed. Um, if you want to do more abstract things like for example, hide the transaction

graph um, by using by encoding the state of your private transactions inside Merkle trees and then using nullifier sets to to verify spend transactions, then you then you need to make quite complicated circuits because then you need to do a lot of like evaluations of Merkle paths inside a inside a Snark circuit. And that's something where something like Plonk whoop, pardon me, uh, really shines. Um, yeah. Okay, cool. Thank you. Um, uh, another another question. Do um like uh, do you think there's uh, a specific hash function or like uh, yeah, hash function that could do work

like better with Plonk uh, than others? Well, I know some that work worse with Plonk. Um, so for example, uh, things like the Poseidon hash function that recently came out which was designed um, to be very efficient in our SCS. It straight up isn't very efficient in Plonk because it basically it uses a large number of additions. But things like MIMC um, should be pretty efficient. Um, I haven't I haven't done any hard numbers but generally um if you're mixing rounds, um, like roughly has you're mixing rounds like I believe that generally the number of additions is quite similar to the number of multiplications in you when you're kind of scaling up your, um, uh,

what's it called? Your cumulative hash value. Um, so, yeah, I think I mean generally, I think I think I I I suspect it'll be about two to three times slower. Well, um, to get some hard examples actually, something that I have done is, um, for example, um, elliptic curve, um, operations on elliptic curves. So, things like baby Jubjub and Jubjub. Um, the efficiency should be roughly basically the number of addition gates you need is about the same as the number of multiplication gates. Um, so then it's only, you know, 2x slower, um, which is pretty pretty good for universal snark, I think, but, uh, I'll let I'll let I'll let I'll let everyone else be the judge of that.

Mhm. Mhm. Okay thanks. So, are there, um, any what's currently like plans for implementation or is should there be more other more theoretical work first or Yeah, so, um, we we basically, um, like uh Ariel Warner and I, we were basically focusing very intently on getting the paper out as we had the idea then. So, um, the kind of the next phase is something that phase I've been, uh, starting is basically, um, actually producing implementations of this thing of this stuff. Um, and I know there's

quite there's been quite a few like, uh, people being quite interested in this and interested in collaborating. So, I'm I'm what I'm uh, I'm I'm hoping that we can get a bit of a like, uh, some open source tooling um, around making snark proofs. Um, but yes, that that's all in its infancy. Uh, I'll uh I'll uh I'll go back in a month. Hopefully we'll have something a lot more concrete then. Um Uh I I think I think I have some like questions about the the proofs in the paper.

Uh-huh. I guess it would be better if I posted in the group, right? Uh because right now it might not be like so easy to discuss in in in the in the video chat. Uh it's a bit more technical. I I I think maybe that I just ask in the group instead of like asking you here. Yeah. what do you think? Um I mean what Yeah, I'm happy to What What you asked there I mean if if it's if it's something which is going to be It'll take take a while to to to verify.

Maybe we can take it offline. Uh-huh. Okay. Yeah, I think it's what he just mentioned there is he said that actually you could say it now if you wanted to. Uh-huh. if it's too heavy. But we will have to wrap pretty soon. Uh okay. Okay. don't we ask this question then we we wrap up. So yeah, go ahead, Cheng Chengwan. Oh yeah, yeah, yeah. Uh cool. So basically in in lemma 4.5 Mhm. uh I'm curious what would happen if the uh P polynomial cannot compute the polynomial T. Because there's uh some probabilities the P polynomial could not compute T.

So I'm going to have to bring up the paper and refresh my memory on the 4.5. Um just give me Wait, that's Sorry, give me a second. Uh Just a minute. 4. 4.5 Is that Mhm. So Sorry, guy can you refresh my memory what what was the question?

Uh yeah, can you go to the proof? It's in the next page. Yes. Uh so here you see you see that in the second second item it says P polynomial computes the polynomial T equals to uh the like the formula. Mhm. But here there's a probability that uh P polynomial cannot compute T. So if I'm remember correctly this kind of thought experiment um so we're saying that Z does not divide F.

Um and so we then wait no that's So let me just try to remember jog my memory about this. So we're working in the algebraic group model which is kind of a little bit of a um a workaround to the fact that Kashi's polynomial current scheme isn't actually simulation extractable if you don't make a couple of assumptions um about your adversary. Um and so the algebraic group model where um the um the the the assumption is the implicit assumption is basically that the coefficients of any polynomial an adversary commits to are efficiently

extractable. Um this is it's a bit of a workaround due to the fact that um blah blah blah um you don't know the maximum degree of um the polynomial an adversary committing to not theoretically at least. I mean you do in reality because the structure of the string only goes so high. But it means that basically you you can't create construct a model where an extractor can always recover the coefficients. You just assume that this is the case. So if P can't compute the polynomial then this would mean that This would mean that so F is supposed to represent some kind of some some like this is this is

supposed to represent some kind of polynomial identity which vanishes the vanishing polynomial. So so I'm just trying to jog my memory cuz this was this was one of the levels that I wrote. By the way, I think I'm going to have to bounce now. So we have to wrap this. Yeah, we can yeah, Now you know at least where to look. I'll I'll I'll why don't we go on an email thread and I'll CC Alan so you can Cool. Cool. Cool. Cool. Thank you. Thank you. All right. I want to say thank you again Zach for going over this. That was awesome. And I will be putting I Adrian, if you can share the link with me, I'll put this up on YouTube and then we can also share it there.

And there are some I think the question that was repeated in the chat was about implementation, but it sounds like not yet is the answer. You'll hear about it when when I when I get it. Cool. All right. So thank you everybody for joining the study club. And feel free also to suggest like if if you guys want a continuation or if there was a piece of this where you want to go deeper. Like we have some really good people here. So I also really liked this format and it might be something we consider doing actually. Just like having the author of the paper actually talk through it.

Yeah, just an idea. All right. Cool. See you guys later. Awesome.