ZK Whiteboard Sessions - Module Five: PLONK and Custom Gates with Adrian Hamelink

Transcript

Uh hey everyone. I'm Brendan. Uh I work at Polygon and I'm here with Adrian. Uh who is a very talented cryptographer. Um Adrian, you went to school at EPFL. Uh you're now at one of my personal favorite projects, Aztec. Um so yeah, really really happy to have you here. It's wonderful to be here. So, today I'm going to be talking about how we create how we actually design circuits for Plonk. And going a bit over the the basics, how they're introduced uh classically with these arithmetic circuits, but how we actually like expand upon that and optimize them to

get more efficiency out of them, and explain a bit like how they actually function in the real world and different optimizations we use. In particular, those are going to be custom gates and lookups. So, I I love custom gates because they allow us to make things like recursion and hash functions and elliptic curve uh signatures and group operations really efficient. Yeah, they're awesome. And they really get to exploit as much efficiency as we can from these proof systems. So, because I guess basically the way they're introduced, right, is it you have these arithmetic circuits. So, generally you have um a finite field, which is like usually

quite large. And we're going to it's often common to write it down as like this this graph with different operations and some inputs. So So So So we call these gates, right? And then the we're using those as public and private inputs. Yeah, I'm going to I'm going to have a simple example with two public inputs and one private input. And the circuit is just going to be computing here we'll have like an addition. So, we're going to add X1 and X2. We'll indicate this with a plus and we'll label it with a one.

Here we're also going to be doing an addition. And noted by two. And so the this private input uh so the difference I guess to to back up between public and private inputs is that public inputs are going to be included with our proof and we're going to sort of mark them as public inputs, but private inputs are not. So, it's private data that we don't want to be Exactly. That could be your secret key or or just general data that you don't want to reveal to everybody. So, I've added here like one multiplication gate, so we have a bit of everything and this one is going to be the third gate.

Now, when we have gates like this, it's easier to think of them as like one operation which takes two inputs, a left input and a right input, and produces an output. We're going to be labeling them the left inputs A1, uh the right inputs B, and the outputs as C. And we're going to do even though this is the same arrow, we're still going to be duplicating it for reasons I will come back to later. And B2. No, this is A.

A2. B2. Numbers are hard. Yeah, indexing is the hardest part of math. For sure. So, the idea here is that we're going to be taking X1 plus X2 and X2 plus W2 and then combining multiplying that result together and that's going to give us C3. Now, this is a very common representation. However, when we actually are building these circuits in code, where it's more practical to think of them in this table form. So, we're going to organize our A values, our B values, and our C values in a column.

And um we're going to look at each gate individually. So, we're going to have three gates here, one, two, and three. And what we're going to want to do is we want to check that all of these values have been com- computed correctly. So, I'm going to prove to you that I've done this computation correctly. So, in this first case, for example, what I want to prove to you So, so so just to back up to this matrix, where in each uh sort of uh cell in here, we're we're actually filling in what the number is uh what when we evaluate the circuit.

The field elements. And C3. All right. So, for this first addition gate here, what we want to check is that A1 plus B1 is equal to C1. The same is going to be true for this one. And for But for this one here, since we've got multiplication, we want to check that A3 * B3 is equal to C3. Now, we can think of these as two separate gates but the way Plonk works is we want to prove everything at once.

And we want to try and find a way of unifying both of these computations in one go. So, So, and and and that's so we can apply it to every row of this matrix. Exactly. So, we can apply Exactly. We want to verify the same type of equation for each row, because that makes it possible to batch all of these constraints in one go. And yeah, we we call um we're going to be applying a constraint over each row, over each gate. So, how do we differentiate between addition and multiplication? Well, there's a simple trick where you use these these additional variables called selectors, and here we're going to be denoting it by S.

And we're just going to say that like if we've got an addition gate, we're going to be denoting it by one. And if we've got a multiplication gate, we're going to be multiple denoting it by a zero. So, I'm just going to add these here. So, one one and zero. And the way we combine these is by this one equation where So, I'm going to denote by I to capture all three rows. Going to be having SI which multiplies AI plus BI plus one minus SI times

AI BI. And here I'm just going to pass the C on the left. So, we have an equation that equals zero. Now, this complicated equation it makes more sense when you actually replace the S values. So, for example, in the first one here, we've got S is equal to one. So, so we know it's an addition gate. Exactly. So, since in S1, this is going to be one. However, this part here is going to be zero, so we're going to be ignoring this multiplied term.

So, in the first gate, we have exactly this with the C1 on this side. However, yeah. Yeah, so so in each row we if we were to be tedious and and substitute, we we could see that we we're enforcing the same constraints. Exactly. And So, yeah. So, so this is the idea, right? You want to have You want to organize a bunch of values which you've computed in this table and have this one big constraint which applies to each row which will ensure that everything you've computed is correct.

Now, one problem is with this representation is that it's not really natural. This theoretical results that say that you can get any you can explain any type of computation using this model. However, when you're actually programming something, you're not actually going to be doing only multiplications and additions. So, it's a very limited set of functionality. What what what are the some of the things that we want to capture that that would take Well, so so I guess to to back up, we we care about the number of rows that we're using this matrix, right? And And why do we care about that? Right. Because the amount of work you're going to be doing when you're creating a SNARK is going to be proportional to the number of gates you

have. And if you only have additions and multiplications, you're going to have to do a lot more work to prove that your computation was done correctly. So, to get these things to work better and faster so people can generate proofs even from their phones, you want to try and reduce the number of rows as much as possible. And the way we're going to be doing this is using custom gates. So, the idea is instead of having only additions and multiplications, we're going to have special types of operations which are going to be doing more specific uh type of work. So, one thing that's very common in SNARKs is you want to replicate some existing cryptographic

like protocols or functions. And these will be commonly elliptic curves or or or or hash functions which are the So, so like checking a signature or Exactly. Okay. And um And so so for like an elliptic curve group operation, it's actually like a a lot of additions like if we write out how many additions and multiplications there are, it's you know, it would be some number of rows. But if we could somehow fit that group operation into one row, then we're saving on our proof time. Yeah. And especially like if you're doing elliptic curve operations, you're going to be doing it this type of work a lot of

times within your circuits. So, you're going to be exploiting that fact and saying well if I'm if I'm spending 50% of my time adding up points or doubling them, then it might be worth it to have a specific part of the circuit which just does that. Kind of like how nowadays you have in modern CPUs, you actually have specific parts of the CPU which just handle hash functions because that's how you get them to be faster. So, that's what we're going to be trying to do here with SNARKs as well. So, it's a specialization like within a circuit for SNARKs. Exactly, yeah. Like little specific computations.

So, um let me I'm going to give you an example which is a very which going to is going to be very synthetic. I want to show you like a kind of circuit you might want to come up with it by yourself. And or like a scheme where you'd use SNARKs. And Mhm. The idea would be to like show you how you might you come up with your own custom gates in order to speed up the specific circuit. And go from a high level how to uh how how you would actually do this yourself. So, let me erase all of this and I'll give you my example program. So, I'm I came up with this like weird signature scheme which

you'd probably never use in practice because it's really inefficient. But it's going to be based on hash functions and specifically not one of those in like new and cool algebraic hash functions, but like a well-established one like SHA or or Blake. And it's going to be really simple. So, to to to generate your key, you're just going to be sampling a secret key, which is just going to be a a set of byte like say 32 bytes. And your public key is then just going to be the hash of this secret key.

Now, because we're working with SNARKs, which are defined over these fields, we're going to want to try and exploit that to ensure that the state the the data we're actually going to be working with is going to be consistent with this model. So, I'm going to be using some weird notation here where I'm going to be putting this little bar over variables whenever we consider them as byte as bits. So, think of this as an array of like 32 or 256 bits. Um but what we're going to be returning is the public key, which is just the representation of these bits. So, you just

We're going to be denoting this by f of PK, which just takes like the binary computes the binary the inverse binary representation of these bits. And So, so we have bits and and we want to yeah, embed it into a field and Exactly. And mapping is like generally one-to-one if your field is rather large, but we we don't need to care about these big details too much. And then what you're going to sign, so I'm not actually sure about these details, but I'm pretty sure you actually need randomness for some theoretical reason with your signature scheme. So, we're going to try to do things properly even though this is

not really what you would be doing. Um so you've got your secret key to sign a message and the message M. We're going to be considering both of these as uh as their bits. And so the first step is you're going to be sampling some randomness. You're then going to be computing the hash of your randomness, your secret key, and your message.

And what you return is the signature, which is just the conversion from binary back into our field. Exactly. And so the problem is if I gave you just a sigma, how would you check that it I actually computed it correctly, right? I would need the secret key. Exactly. So the way we do this is that we're just going to create a snark, a circuit, which will attest that I computed this function correctly.

Now, I already have the outputs and stuff. So I'm going to have to recreate like ensure that my circuit checks that all of these um all these operations were done correctly. So um yeah, I'm going to write this here. So we're going to denote our circuit here C. And it's going to have public inputs, which are the inputs that I would actually share with you. So what are they? It's my public key, which is given by in as a field element, the message, and the actual uh signature.

And as private inputs, well, what is private which I've used here? I've got the my secret key, I've got and my randomness. So I'm going to be denoting here these here. So there's a couple of things you have to watch over when you're designing circuits, right? Because it's really easy to forget some constraints, and you end up creating a proof which proves nothing. So, yeah, we we we really don't want our proof to be valid for every signature.

Exactly. So, we're going to have to check a lot of stuff. The first thing we're going to be doing is we're going to check that all of these binary elements are actually in binary. So, these will be given as like these big arrays of individual ones and zeros, but we actually have to check that these are ones and zeros. So, what what what we've got our we've got our secret key, and we've got our message. We need to ensure that these actually are given as bits.

Now um inside the circuit, we're going to be creating recreating basically the signature, and actually computing the hash function. We're just doing the exact same thing as here. Which is R, SK, and M. Then, um we also need to make sure uh we need to make sure that this the the public key corresponds to the secret key which is being used here. So, we're also going to be doing that. We're going to be computing the public key from the secret key.

And finally, so we've computed these two elements, but they don't the public inputs are the actual field elements. So, we don't need to ensure that um if we take the binary representation of our public key. Then it matches with this public input here. And if we take And the same for the signature. There we go.

Let's get this properly. Right. So, we're checking that the public key is consistent with the private key. Essentially a proof of knowledge. is Yeah. Yeah. Yeah, I mean it it it sort of I mean it's similar to an elliptic curve uh uh signature just with it difference in key generation and Exactly. Like you can notice a lot of similarities with this and that's why I didn't want to deviate too much. Um And so, when I sign here, what I'm going to be doing is I'm going to be creating an additional proof, which is just we'll call it snark that's proof with all of these public inputs here.

And when I'm going to be verifying the signature, I'm going to be just doing the snark verification of the circuit using these public inputs and that's going to essentially be my verification again. Now, why did I pick this weird example? Um there's two things that are interesting and which are actually like not very non-trivial to do inside the snark. Um the first is we're going to be working with like binary representations. And well, there's ways you can do that with the classic uh plonk representation.

You it's not you're not going to be as efficient. You're going to be spending quite a few gates being making sure that um that you've decomposed the stuff correctly. Yeah, because we need to go from uh we we need to basically prove that like a linear combination of some field elements correspond to bits um equals the field element representation. Mhm. Exactly. And so so that's like a lot of multiplications and additions. Exactly. You You've got to like if you if you map it out, you've going you're going to have like the first bit times one plus the second bit times two, etc. So, it's a lot of additions and multiplications, but it's a very similar structure. So, this there's something you can work with. And the other thing I'm going to be talking about later is how do we actually

compute these hash functions inside of a circuit? So, hash functions, especially like SHA, were designed for hardware. And so, they make extensive use of like XORs, ANDs, all of these things that are very fast in hardware, but which are terribly slow inside of circuits. So, we're going to see how we can optimize that. All right. Now, going to send it I'm going to talk about how we're going to We're first going to touch on the the binary representation part, okay? All right. So, let's talk about how we actually decompose stuff into binary.

Now, I know we mentioned that we're working with 256-bit values because that's what you need to be secure, but that's going to be a lot of stuff to write down. So, let's just say we have three-bit values. It's not going to be a very secure signature scheme, but yeah. Just a warning, don't implement this in production. So, let's say we have this value C, which is given by three bits. Which I'm going to label I know they're reversed, but as I promise, this going to make sense. How do you actually cap This is going to be an element in this binary um set.

The actual value of C is going to be C3 plus 2 C2 plus 4 C1. Now, there's a reason why I reversed this is because we're going to try and find a way to more to to write this down in a way which will make it more efficient to apply the same computation in multi at multiple steps. So, what we what we do is we just like here we're going to factor out the two out of this part.

plus two times So, here we have C2 plus 2 C1. But, wait. C2 plus So, here we'd have 2 * C1. However, I'm going to just I'm going to add a little extra term here. I'm just going to add 2 * 0 to illustrate a point. You can see that if No, I'm going to write all the parentheses here.

You can see that there's this kind of repeating structure, kind of recursive structure, where you're taking a bit, you're doing 2 times something, and then but it's the same thing here, right? You're taking the second bit, you're doing 2 times this other result. So, I'm going to write down some the different steps you'd actually do to compute this and trying to do as not that many operations per per iteration. So, I'm going to start out I'm going to define A0 as zero. Then A1 is going to be C 1 plus 2 times A0, which if we replace is just equal to C1.

Now A2 is going to be equal to C2 plus 2 times A1, which again, if we replace, we get C2 plus 2 * C1. And finally, for A3, we have the same thing, which is equal to C1 plus 2 C2 plus 4 C3, which is equal to C.

Uh Yes. Again indexing. Um wait, this one is one and this one is a three. There. All right. That's right. Yeah. Yeah. Um So, what we notice here is that for these three values, we're we're doing the same operation, right? We're taking the If this is AI, we're taking the i-th bit and we're adding two times the previous A.

So, we kind of have this the same structure we had before with the additions and the multiplications, right? We have the same type of operation, which is repeated over and over, which make it easier to batch. However, we've got this A0 here. And we're going to see that like we're going to try and group things around these three values and do something different for uh the zero. So, just like before, I'm going to try to organize stuff in in a table, um which is going to be more which is going to resemble more like how you'd actually order your stuff in memory when you're actually programming stuff.

All right. So, we've got our four 2 3 Start at zero this time. Um we're going to have This time we're going to have two instead of having left, right, and output vectors, we're just going to have like two vectors. The first one we're going to call B for like bits, I guess. And the second one we're going to call it A for let's call it accumulation or advice maybe.

So, we're going to set B0 to be the actual value of C. B1 is going to be C1. B2 is going to be C2, and B3 is going to be C3. Now, for the A, we're just going to be using these values we've computed correctly. So, the first one is going to be zero. Second one, A1 is equal to C1.

A2 is equal to C2 plus 2 C1, and A3 is equal to C. All right. So, in the SNARK, I'm going to have to send you I've got all these values, and how do you check that everything is correct and consistent with each other?

So, there's a couple of things we need to do. Um first of all, we want to check that these three bits are actually bits, which means we want to check if they're either ones or zeros. So, now I'm going to add over here a list of constraints we want to enforce over the values and in which rows they actually apply. So, for these three rows, we've got B1 um I'm going to write it B1 squared minus B1 is equal to zero.

B 2 squared minus B 2 is equal to zero and B 3 squared minus B 3 is equal to zero. Now, why did I write this in this weird way? Well, you can you can always write it as B you can factor out the B's. It could be times B minus 1 is equal to zero and this equation is only valid if B is either zero or one. So, this is why we've written it in this way. But, what's interesting is we're using a higher degree constraint for Exactly.

So, before we also had degree two constraints because we had A I times B I. But, here we just we we only have two wires so we can actually do the squaring here. Um we don't want this constraint to apply to the first row because B zero should be equal to C. Now, the second constraint we want to enforce is that these three A A 1 A 2 and A 3 were computed correctly. So, this is where we're going to be using this formula here where we want A 1 Again, I'm going to be shoving everything to the left hand side so that it equals zero. So, we've got A 1 minus um

B 1 minus 2 A 0 is equal to zero and same for these two other case. Okay, A 3 minus B 3 A It goes so much faster when you do this in software. All right. Now, you can check it out yourself by doing the computation on the neighbor, but if this is true, then that means that like we've computed A1 correctly. But, we're still missing two parts.

The stuff we haven't verified yet is that A0 is actually equal to zero, so we have to enforce that. And we also want to make sure that uh the value which we've accumulated, this A3, actually corresponds to the value we've had here, B0. So, I'm just going to write this down in the first row. So, we want A0 to be equal to zero. And we want B0 to be equal to A3. All right.

So, why did I do the all this complicated stuff? So, there's a couple of reasons. First of all um we've introduced some new like vectors of values. And this is only going to be one subcomponent of our entire circuit. So, you can imagine that afterwards you're going to have like other um like other constraints, and we're going to be using selectors to either activate all these constraints or deactivate them depending on where we are. So, in in addition to saying if we're doing the multiplication or the addition, we're also going to have these selectors saying, are we doing actually this bit manipulation stuff?

Are we checking in these rows if uh if they're bits or not? Because yeah. And even within this this subsection, we're going to have to differentiate between are we checking uh in this index 1, 2, and 3, or are we checking in this index zero? Sure. The other thing is, so the way Plonk uh circuits are created is that you're able to enforce that certain values are the same. So, you would be able to say that like using this wiring argument or copy constraints as sometimes referred to, you can say that this is uh like B0 is equal to C0.

But, that means that you're you're going to be doing work which is proportional to the number of columns which in which you're checking the values are consistent with each other. However, here we don't actually need to use these any these values A. We don't need to use them anywhere else in the circuit. We are only interested in the bits. So then is we can exclude this column from this copy constraint or this right wiring constraint arguments. The other thing is is that like we're essentially performing the number of of rows we have for this is going to be exactly the number of bits plus one. And

we can extend this. We can we can add other like we can decompose more bits and stuff. Um But so now what we're going to be doing is looking how do we go from this to actually embedding this inside of a Plonk circuit? How do we like How do we actually get a SNARK proof for it? Okay. All right. Adrian, take me back to group theory and roots of unity. I thought you'd never ask. All right. So we all know that SNARKs are based built on polynomials and in particular Plonk uses Lagrange interpolation. So the polynomials which you obtain by

interpolating these values in these columns like the AIs and the BIs and stuff. So one thing we had in in in these constraints is we refer we were referring to values from the previous row or three rows ahead. So this is a really interesting property that we have in Lagrange interpolation is we can access shifted evaluations. So let me just briefly recap what I'm talking about. So when you're inter- when you're doing Lagrange interpolation, especially in Plonk, you're going to be using the roots of unity. So you've got to set H which Well, since we have only four rows, let's only consider four values. So, you've got like uh you've got a root of unity, which is

just this value, which um So, wait, let me just write this down. This is equal to one. Which is equal to omega. I guess W or omega, depending on your preference. Omega squared and omega three. So, this value omega is special because uh if you put it to the fourth power, then it will equal one again, which is actually equal to the zero element. So, by increasing powers like that, you just like end up cycling over everything again.

Now, when we interpolate, we're going to have these four polynomials L0 of X, L1 of X, and etc. And these Lagrange polynomials satisfy really interesting property is when you evaluate the Jth polynomial in the Ith root of unity, you always either get one if I is equal to J and zero uh if I is not equal to J. This reminds me of our selector polynomials.

Yes, this is very closely linked. Um we use this property often for like optimization. Um in particular, one like tiny thing to notice is that these are very efficient to compute, even though they have may have a large degree, you're able to evaluate them very easily, and we can actually like evaluate them as a verifier, um um which saves on computation and com- communication complexity. Now, we have this these two vectors AB. I'll just consider the A1 because that's the one we're actually interested in. So, we had A, which is just four field elements, and we're going to consider um That was an athletic uh I guess so.

Um we're going to be considering its um the polynomial of lowest degree which agrees with A when evaluated in these different points. So, we're going to use this tilde notation to differentiate between vectors of elements and uh and the polynomials. So, it's really going to be just like A0 * L0 X plus uh A1 times uh one of X and like that.

So, if we using this property, we see that like A of uh omega squared, for example, um or let's do the one cuz I didn't write the square. Um if we evaluate L0 at omega one, that's going to be zero. However, uh the only place where it's going to be one is going to be one, so we we have A1. So, it allows us to pick out values. Exactly. We can we we we get exactly the value we want from the polynomial. Now, we were using these like I minus ones and I plus threes and so on. So, the idea is like if you if you write things slightly differently

and you've got we're going to write say we want to like access the Kth element either in front K can or or or pre the previous value. And so, K can be either positive or negative times omega I, what we get is A of I plus K. Now, this is very going to be very useful uh because I'm going to be writing down what we had in the previous slide, uh hopefully correct this time. And uh how we can basically batch all these constraints into one um into one big polynomial equation.

So Now, let me erase the board and we'll get to that. Um So I'm going to be reordering like transposing table where I'm going to be writing each type of constraint. So we the first type of constraint we had was the I guess. Just call it binary. Which ensures that the BIs are binary. Next, we have um the accumulation. Constraint which is checking that the A1, A2, and A3 are computed correctly.

But we also had these two constraints on A0, B0, A3, etc. So I'm going to call Oh. I'm going to call it like accumulation in it. And accumulation output. Now uh first thing that's useful is to map out like where these constraints apply. So as I mentioned, the binary one applies to indices 1, 2, and 3. So I'm just going to write like this.

And however the input and the accumulation, we put them in the first row. So we're going to put a zero here. Now maybe I'll just rewrite the actual row constraints that we have. So this this one was like this weird BI squared minus BI is equal to zero. For the accumulation, we had AI minus BI minus two AI minus one. Um for the initial accumulation accumulator you know, AI is equal to zero. And for this last one, we had B0 minus

A let's reuse the eyes. Bi Bi plus three equal to zero. I use these eyes because we want this constraint to apply everywhere, but we we're going to restrict it to apply only to where the places where these indices are valid. So in this case for example, what we really have is B0 minus A 0 plus 3 is just 3. Now just like we do with the interpolation over A's, well we can just simply interpolate the vector which is going to be one in indices one, two, and three and which is just going to be zero in index

zero. So reuse our selectors here and selector that's going to apply is S till the X. And here again to get the inverse we do this one minus trick. Okay. So now we can actually like write down these the polynomial constraint for these four equations. Now I'm going to write them down.

So it's going to be B X squared squared minus For this one now, this is where things get tricky because we're accessing this previous element. However, we saw that if we have um if we multiply this if we separate out the the the the the evaluation point uh with a shift, then we can actually um access the value from the previous row. So that's what we're going to be doing. We're going to be writing Ax minus 2 A And here, this is a tricky part. We're going to take the inverse, so minus one times X. Because we had the

W K or omega I omega K shifts by K and so we're uh Exactly. So, if we evaluate this one in say omega to the power of one or omega, then this one would be A1, B1, and two A0 which is what we want. Yeah, because we're evaluating all of these over the row and we need to get a value for that row. So, these polynomials really allow us to combine all of these different constraints into just one polynomial equation.

By the way, this polynomial isn't actually zero equal to zero, it's equal to zero over H. For to be precise. So, here we just have A0 uh A0 is equal to zero, so the when we evaluate this polynomial at zero to the omega to the power of zero, we want to get uh A0, which should be zero. And finally again, we use this shifting trick. And what we do is we now shift by three rows down X.

So, this seems like a lot of work, but when you're actually like creating a proof which what one thing you need to pay attention to is how high of a degree these polynomials actually are. And as we mentioned in the normal arithmetic gate constraints with like additions and multiplications, we had one multiplication uh times the selector, so the degree was three. Here we also have a selector and we have a degree two, So, the overall complexity of our global constraint is going to be the same.

Um However, um we're now doing all of this stuff in one go. So, that's That's essentially what I was talking about in the beginning where you're trying to pack as much computation into a single gate. Mhm. Um so, yeah, let's There's one drawback to this approach though. Which is that now these A uh these shifted polynomials, like they are actually different polynomial This is This A tilde with uh omega minus one is actually different from this one.

And so, when we actually open up our value when we're actually proving it, we're going to have to open up this polynomial evaluated in a point. So, let me let me briefly go over this. What I mean. So, you're saying that there's an additional cost when we uh Yeah. access custom gates unfortunately don't come for free. And the additional cost is going to be uh in terms of the proof size. We're going to have to slightly increase uh the proof size to be able to handle these shifts properly. So, proof size and also proving time if we uh increase the degree, but Exactly.

Um And by the way, like you'd probably include this along with those multiplication addition gates. So, you are going to be doing more work, but it's not going to be proportionally much more than what you're doing before. Sure. Sure. Yeah. All right. So, let's maybe uh mention like how So, now we have a bunch of these gates, right? We have the addition multiplication and um and this binary constraint. But, this binary constraint has like four different components to it. So, what we want to ensure is that all these constraints are satisfied all together.

And the way we do this is that we show So, we have this like large polynomial uh f of x, which I'm going to write down short version and um So, let's say we just have like a multiplication gate uh or maybe not. Let's just do the the how how do we Let's just show how we batch together these uh these four types of constraints and maybe just focus on like this ones which are simpler to write.

Um So, um let's assume that the during the creation of this proof, we get a challenge gamma from the verifier. We want to ensure that these polynomial constraints all vanish over H. So, the way we do this is that if we've got, for example, like the binary constraint B. If you've got this one, the way we show that it it is valid when multiplied, obviously, by

selector. To show it vanishes on H, we are going to be computing what we call the quotient Q of x, which is f of x divided by x ^ 4 - 1. Why do we take this x ^ 4 - 1? This is because if you take any of the roots of unity and you put it to the power of 4, this expression will equal to will be equal to zero. However, if when you evaluate f uh in uh omega, omega squared, or what have you, this will also be zero. So, that means that this polynomial actually exists.

And we're going to be sending over this polynomial Q over to the verifier via a polynomial commitment scheme. And what the verifier is going to be doing is it's going to sample a random point, say Z. It's going to check that Z 4 - 1 times Q of Z is equal to F of Z. Now, I purposely didn't go I I'm going to come to like this complete F of Z. Because this F of Z is really symbolic. What the verifier has is commitments to these B's, to the S's, and to the A's.

Um and let's here write down now. Can you use a different color? Something like that. We're going to be multiplying these different constraints by different powers of gamma. So, here let's let's just focus on one of uh the constraints. Let's take the the the the last one which um is B Um what was it? A And this one is the other selector one

that's S. And you do the same for the other constraints, but for lack of space we're not going to consider them. And you use different powers of alpha. Now, in order to actually evaluate F of Z, what the prover is going to be doing is it's going to be evaluating Let me It's going to send evaluations of B Z of S Z Um and a omega three.

See? And for the other constraints, we're also going to have to include a z and a omega minus one. Using these four five different evaluations, we can recompute a full evaluation of f. And if this equation is valid, which is what the verifier is going to be doing, then we know that or at least with very high probability, thanks to the well-known Schwartz-Zippel lemma, that uh the equation must hold over all x's in this uh over all omegas, and that therefore our

constraints are satisfied over each rows. And obviously for soundness, we're sampling z from the entire field. It needs to be a large enough field, and you're In practice, you're going to be making it non-interactive using the Fiat-Shamir transform, which also has its well-known quirks, I'd say. Um but yeah, these are all details which uh are not really important for custom gates.

All right. So, what have we learned so far? Let's recap. So, when you use custom gates, what are you actually doing? You're you're you're trying to cram more computation and being able to you want to specialize the type of your work you're doing. And the end goal is obviously to reduce the number of gate the total gates you have by having more complex gates. Now, this is especially useful in the context of SNARKs when you have the same type of operation that's being repeated many times. And so for this example in our example signature scheme, um you you're doing a lot of binary

decomposition. So so this is a That would be a good use case for this. Um the way we design these custom gates is going to be using these shifts, which are really cool properties of the Lagrange polynomials. And these are are are are used in several places in the Plonk proof proof system and they're very powerful. However, they do come at this increased proof uh complexity cost, like the proof becomes larger because you're sending more evaluations of the polynomials. Uh and the verifier, I guess, is doing a bit more work. But this work is still going to be constant and it's it's a it's a it's always going to be a trade-off. Like when you're designing these, it's very much an engineering challenge and you've got to figure out like what makes sense, you've

got to benchmark, and try things out. Well, there are so many different parameters that we can optimize. Like do do you optimize for uh like the width of our circuit, like the number of columns, or do we the number of rows, the degree of our gates, and so on? Yeah. And sometimes it may make sense on paper, but when you actually run the benchmarks, you're going to be like, "Oh, maybe not, actually." So this is going to be a lot of tweaking, but this should give you a good idea of like how you might actually design these gates by yourself. Now, yeah, you mentioned it before that like these are heavily used in elliptic curve operations or um I think you guys also used them with your algebraic hashes. I think you guys used Rescue in the previous versions of Plonky right?

Uh Poseidon. Poseidon, yeah. Yeah. Don't we we can't talk about algebraic hash functions around Ariel? I know. I Hopefully he doesn't hear us. Shout-out for life. All right. So, custom gates are only one small uh are are one part of like how modern circuits are designed. Um even in our example, like you're not actually in real world circuits, we're no longer really representing stuff in binary because it's not very efficient. Um however, uh you might still be decomposing stuff into into limbs. So, as we had like C is equal to uh C3 plus instead of having like bits,

we can have like say bytes. So, which would be multiples of 256. So, 256 plus uh I don't know. C2. C2 plus 256 squared times C3. This will make it a lot more efficient because you would have then uh eight 256 times less rows. Um but the problem is that before we were able to prove that these C2s were binary. So, uh we had this like BI squared minus BI.

However, if we wanted to prove that CI the these CIs were between 1 and 250 0 and 255, we'd need a multiplication of 256 uh terms, which would be basically impossible, I think. So, this is um lookups are going to give us a way to constrain these CIs to be within a certain range. Uh and this is something very often comes up in SNARKs. It's like being able to to range range check elements. Well, especially when we're dealing with cryptocurrency because we don't want overflows. You want to make

sure that stuff is like bounded and that like your additions are probably checked and so on. So, this is really important. And um so so so lookups are going to give us an efficient way of uh doing these range checks. Now, the other thing lookups are really cool is that they're going to allow you to create kind of custom gates, but you're not actually going to be computing anything. You're just going to say So, in the example of like a a a real hash function uh where you would have So, let's go back to like the notation from the beginning where you have left, right, and output gates. You want to show that

CI is equal to the XOR of the values AI and BI. Now, uh for a quick reminder, like when you're doing an XOR, um so, for example, if you if if AI and BI are bits, well, uh 0 0 is going to give you 0, 0 1 is going to give you 1, 1 0 is going to give you 1 and 0 uh no, 1 1 is going to give you 0.

Now, this is very easy to do in hardware, but inside of a circuit, this is going to be hard. And also, we just said like we want to be able to use larger decompositions like bytes and stuff, um which is is going to be really complex to do and with only additions and even custom gates. So, instead, what we're going to be using is what we call lookup tables. The idea is that inside of our our table of values, we're going to be including some other um some new columns, column T1, T2, T3.

And what we're going to be storing in these is going to be all possible values that we would get if we're performing in this case an XOR. So, um So in in this easy in this case where we have bits, we have only these four rows, which are exactly these. And the idea is that when you have when you want to actually compute this equation, you're going to be show what you instead of do instead of actually computing it, you just want to show that AI, BI, and CI is one of the rows in these values.

And this is what we call looking up. So, in this example where you have only four bits, it's not going to be very interesting, but we can have like we can make this table a lot larger. And for example, consider all possible uh pairs of 256-bit numbers, which would be 2 to the 16 possible possibilities, and we're going to all write these down in this large table. And whenever we have um uh whenever we have this type of of constraint, the a lookup argument is going to enables allow us to say, "Well, this row is valid if and only if it exists somewhere

in this large table." So, this is really like the two main use cases for uh lookup tables in the in SNARKs. The one problem is that these tables are usually going to be really large. As I mentioned, 2 to the 2 to the 16. I think circuits nowadays are like bit like maybe a million gets to 20 or something. Like we're approaching some pretty like pretty large numbers and you're going to be doing lots of computation. Um so you're going to want to design like choose uh a specific like again engineering wise like choose different table sizes, what do you want to include? Maybe you actually might want to include a instead

of 256 uh values you might want to actually a few like only 128 because that means you can have like uh other entries inside of the table. So I'm not actually going to go over how this argument works. Um but because at least to me I find it very complicated and it doesn't really allow you help you understand like how you're going to do lookups. Um however, I will mention that um the way this started was with the Plu up protocol.

And the Plu Plu up protocol is it looks a lot it's basically an extension of Plonk where when we're doing this quotient testing thing, we can include other terms again by like multiplying by powers of gamma. And in in in the classic Plonk paper, we had one extension was the ability to check that mult so when you have your your table of A B C, you're able to enforce wiring and to say for example that A1 is equal to B1 of B2 which is equal to C1.

And uh let's say that so so this would mean that the input at the first gate is going to be the same as the output and that the output is then going to be used as the right input to the second gate. And so you you create these like cycles in your table. And this the way you prove this is by constructing these these weird special polynomials, which I think we call grand product polynomials. And essentially what what what it's doing is it's performing a product check. So we're going to be constructing this vector Z

uh of length n with Z1 Z2 Zn and and we're going to show that like multiplying uh multiplying all of these ZIs is equal to one. And so that's something that's like that we know now how to do. It also uses these shifted properties. And the the Plonk Up protocol is quite similar in that way. It's also going to be um using the fact we're going to be constructing another type of polynomial Z like this, which which should also satisfy this fact that uh uh the product of all its terms is equal to one.

Um however, yeah, I mentioned that the big problem is when you're creating uh when you're using these lookups is that you have a large you might have like really large table and the amount of work you're going to be doing as a prover is going to be proportional to the number of entries. So you have to be careful to not include too much precomputation because otherwise you're always going to be performing that amount of work even though you're only looking up a couple of entries inside of it. So you'd have one So so for for for for range constraints, for example, if you want to just prove that it's a 64-bit value, you'd have to have a table size 2 to the 64, which is again really hard to do. So you're going

to have to like find a balance with it. However, this is something that's being actively worked upon and researched. And just recently, a new paper came out called Kalk, which by folks from the Theorem Foundation. And that paper promises like some some improvements which removes this limitation from the large table size. And hopefully, that means that we can have like SNARKs now with lot more with much larger tables even though we're only using a few entries.

And hopefully, that will make help us make us allow us to design like way more efficient SNARKs. So, yeah. I think I've kind of gotten to the end of what I wanted to talk to you about. Again, all of my all this stuff is like not there's more to give you an intuition about how how you could come up or how we actually come up with the these circuits. And maybe demystify a bit like all of these terms. Um yeah. Yeah. Custom gates not so scary. Yeah. Hopefully.

Well, cool. Yeah, we we went through basic circuits, custom gates, binary decomposition, Lagrange, polynomials and shifts. Covered a lot. Lots of stuff, huh? Yeah. Like don't hesitate to look at papers also for more details. The slides should be available. And yeah. It's good talking to you, Brendan. Thanks, Adrian. Likewise. Uh just want to say thank you to Aztec for letting us use their beautiful space. And we're going to follow up with a short interview with the inventor of Plonk himself, Ariel Gabizon. Ooh, looking forward to that.