PIL: Polynomial Identity Language - Building the Engine of the zkEVM

Jordi on on stage and Jordi's going to be talking about Polygon Hermez and especially introduction to the polynomial identity language. So without further ado, let's welcome Jordi. Hello. Hello everybody. Thank you very much.

Uh let me share my presentation right now. Well, first first of all, before starting, I just want to well, welcome to the to the Polygon Zero people. Uh it's a luxury to have them on board and uh very excited to work with them. We're already as as as as Daniel and Brandon already said, we're having already working with them the last in the last weeks and has been very productive. And I also want to thank you to the to the to the Polygon founders for setting up this collaborative environment in the technical things.

I think that we can go much farther together helping one each other as as a team. So it's going to be very incredible and and I'm sure that we are going to scale Ethereum that then is the goal that we have all together. So with that said, I'm going to present today the PIL just to understand where the PIL fits in the in the in the project. Well, uh Let me just here a second. Just I can see how Okay.

So the the the idea of So the most critical thing for roll-up is generating this proof. Generating this proof is is is is quite hard, but the idea of this proof is we have a note state, we have a many transactions in the case of Hermes, we have a normal Ethereum transactions, we want to one we want to be EVM compatible by code by code. We don't want to compile or using the compiler, we just want to implement the actual by code. So we have normal Ethereum transactions and we want to create a new state root, okay? So building this circuit is this deterministic program or this circuit is the the the challenge.

So to build this circuit, what we what we do is we have a mainly well we are the approach that we are built that we're following right now is we're building a stark and then in order to reduce the gas cost to 300k or even lower is just to verify this stark with a plonk or growth 16 proof. Okay, so this is the the the main approach and um the the fact of using starks this this is a little bit game-changer between traditional R1CS systems like plonk or growth 16 and more polynomial polynomial base. This is in in comparing with electronics, this is just working with normal and or normal gates and you just put them a lot of them or when you introduce the clock. When you introduce a clock in the circuit, you can reduce the same electronics and run many cycles. So here is where the polynomials takes a very importance.

You when you read the word polynomial, just understand it as a array of values. At the end a polynomial is set of values. You know a line, you can represent a line by two numbers. Well, you can represent a a big polynomial with many numbers. So you have to understand the values and this works well in this concept of clock of a step.

So you have a state machine and every time in in state machine you have a new value and this is represented by a polynomial in each step, one one value, and so on. So, and and the idea of defining the of defining this prover is that we need to define we need to commit to a set of polynomials, and then defining a set of relationships, identities, between these polynomials in order in order to build these state machines that work together. And here is where the polynomial um identity language, this language that we created for creating these special relationships between polynomials and building these state machines. Okay? Uh What with this relationship, with this set of relationship, with this compiler, this will be used for generating the STARKs, for generating the the the the prover of the STARK, and then the verifier of the STARK.

Okay? So, to start, I think the best way to understand how this polynomial identity language is just work just do an example of how this works. Okay? Let's start with what would be the hello world of this language. In this case is we are defining a very simple state machine that actually computes 32-bit numbers through from two numbers of 16-bit numbers.

So, it's a state machine that has two steps. Okay? So, we just even steps and odd steps. In the even step, we just uh get a number and put it in a register, and in the second step, we just shift the register and add the second number. And then with and then we start over again.

So, we can generate as many 32-bit numbers as we want. So, we have one register, in this case is one state variable, in this case is out, and we have one input that it's a value that we can put at any state we can put the value that we want. We can put new each value, and every two steps, we are generating one new 32-bit numbers. So, how we would be write that in PIL? Okay, I was this is would be as simple as that.

We have a constant polynomial is a constant polynomial that's so the first is the first number is one, the second zero, one, zero, one, zero, one, zero. This is it's the instruction what is doing. Okay? We have the frame that the input of the system, the number that we freely can set to any number that we want and we have the register itself, the register out. Okay?

So, in this and then we are start defining the constraints to these polynomials. The first constraint is that we are forcing that frame is a third it's it's a 16-bit numbers. Okay? In this case, we are doing it's included in another constant polynomial that we have defined it here in the on top that includes all the numbers between zero and FFFFFF. So, all the all the 16-bit numbers.

Okay? So, with this we were empty that the frame can be any number but just between zero and zero X FFFFFF. Okay? And then we define the the the constraint for this state machine. Actually, we are saying that the next step must be if it's if set is one, if it's so is the first step, then this is going to be one, the second part this is going to be zero.

So, the first if if it's one, we are just putting the input to the to the to the register. Okay? If a set is zero, so it's the second step, then this is going to be zero but this second one is going to be one and then what we are doing is we are shifting the out and adding the frame. So, every two steps we are generating a number that we know for sure that's going to be maximum 32-bit number. Okay?

So, we define it this this this way. Okay? Let's move to a more complex state machine. This case, we are going to define state machines that generates groups of five numbers of 32-bit numbers that fulfills this relationship. A * B + C must be uh D 2 2 to the 32 + E.

Okay, so we are dividing this most significant bit and less significant bit. We're doing the arithmetic operation. This case is a multiplication and a division. Okay? So, how we do that?

Okay? We have a state machine with five registers, A, B, C, D, and E. And the idea is that uh in in the in the in the five first steps, we are just latching. We are setting We are setting We're putting the the input. We're setting these registers.

We're setting A, we're setting B, we're setting C, we're setting D, and we're setting E. And once we have all the registers set, then we force the condition. Okay? When we have to force the condition? Well, we have this second this this this this next polynomial, we call it latch.

That's actually when you want to force that this condition fulfills. So, we have a state machine where you just uh load uh um five numbers, and then you you you are forcing that these five numbers are uh fulfills these um condition. So, how would we write that? Well, we would write this We have these constant polynomials, set A, set B, set C, and set D, and set E. We have also the the the latch polynomial, okay?

And we have also the frame, it's the input, and then we have the five registers. Okay? And how And here we start adding the the constraints. The first constraint is we say frame must be a 32-bit number. Here we Here is the the first thing that it's important.

We are using the results of the other state machine, the bytes4.out. So, this this frame must be a number that must be included in the bytes4.out. That means that this number must be a 32-bit numbers because we have the conditions that we generated in the last state machine.

Okay? Then we do the next Then we calculate the next state machine in case is the A' prime B prime C prime and D prime and this is if set A is one then we just set the free into A and if it's zero we just keep the last value. Okay, so this is the conditions for the next A B C and D. Okay, and finally when latch is one we must fulfill that mulsum is zero and mulsum is like an intermediate polynomial that we say that A times B plus C minus D to 232 plus C is is and this must be zero in order to fulfill this this operation when latch is one. So here we just define it a state machine where we can do arithmetic operations.

In this case is this addition plus so here you can do a an addition just if for example setting B to zero or you can do a subtraction by setting A and B. We'll see in the next in the next example how we will how how we use this arithmetic um circuit. So let's now build something more complex, okay? Let's build a a computer. Let's build a state machine that actually execute instructions, okay?

So here we have five state have five registers, okay? We also have an six register we call it the program counter. Actually it's the line that I'm executing. This is another register that this is in this state machine. We have a bunch of polynomials that are the that in somehow they are the instruction that I want to execute, okay?

We'll see these polynomials how this work but this is the instruction, okay? We have also frame, okay? And with this we have a state machine to go from A to A prime is the next state of A and we are evolving. We are executing. We can put any instruction that's defined by all these bits that that compose the instruction and we are executing this, okay?

So let's see different instructions how this would work, okay? Well, first in the definition would be just we define all these all these polynomials, okay? The same way that we saw before, okay? We define here a set of So, for this these instructions must fulfill some initial conditions. For example, we want that in A be binary.

So, we say that in A * in A - 1 must be zero. Here, the only condition for this to happen is that in A is either zero or one, okay? We want free in to be also a 32-bit numbers. We have in we want also the constant to be also 32-bit numbers, but in this case we write an offset just so that const can be also positive and negative. It's a 32-bit numbers, but uh signed positive and big numbers, okay?

And the we have the address that just 16-bit numbers. It's the byte two, the one the first one that we we have, okay? So, let's do let's start with instructions that move from A to B or from B to A or something like that, okay? For this, there is part of the instruction that's it's in in A, in B, in C, in D, and in A. Here, we have these are selectors of which register we want to have this intermediary register, we call it top, okay?

So, the idea is we we load uh from A, B, C, D, and E, and we load to up, okay? This is the first line of the polynomial internal language. So, if in A is one, then we load A. If in A is if if in B is one, then we load D, okay? We add them together.

We can also set a const. We can also put a a constant value. So, the instruction can have a lot of constant value. For example, if you want to put an seven in register A, then const would be would would be value seven, okay? And we also can select the the the the the free in, okay?

And we set we have these set values to A, B, C, and D. So, for example, if I want to move from B to C, then in B would be one, the other since would be zero, the const would be zero, okay? And the set C would be one, and the set A, set B, set D, and set E would be zero. Okay? So, in this case, with this will fulfill this relationship.

If I want to put a seven in D, then cons would be seven, all in A, in B, in C, in D, in E, and in free would be zero. And the set D would be one, and the other sets would be zero. Okay? And this is how we define in Pillo this instructions. So, the instructions for moving.

Okay? We can also do conditional jumps. Jumps and conditional jumps. This case is we have a circuit. We are I'm not going to enter in detail how this works, but we have a circuit that's determines if the operator is zero or not.

Okay? And if it's zero, and the instruction is a jump, okay? Then, instead of loading the program counter to the program counter plus one, we just load a new address. So, we do conditional jump in here. Just by defining how So, by seeing how by by changing how by defining how we set which condition must the program the next program counter must must must fit.

Okay? So, we have also So, we have conditional jumps. And we want to do also arithmetic operations. We can do want to do multiplications, additions, and so on. And and And how we do that?

Okay? And this is probably the most important slide of my presentation. Okay? Because this is the the trick and and the main thing that we're doing here. Okay?

So, we here is we are connecting the last state machine, the state machine that do operations, and with the the main state machine. When the main state machine, we have the the the instruction arithmetic. When we have when we first we have this arithmetic instruction, then we are saying that the the the values in A, B, C, D, and the the op operator must be included in the last state machine arithmetic A, arithmetic B, arithmetic C and So, somehow what we are doing is we are connecting we are we are saying in in the main in the main state machine we are assuming that some arithmetic function is okay. Okay, so we can set up freely. We can put the values in the registers and we are saying, "Okay, this condition must be fulfilled."

And we assume that this is okay. But this is because this is delegated the the verification of this is delegated to the other state machine. Okay? And this concept of connecting different state machines with the block up, again, thank you to the Affect people with the block up idea. This is a great thing.

This allows us to connect these state machines and this is what allows us to do engineering. We can generate like many state machines that are doing different things and connect them all together. Okay? So, um Yeah, this will be of course now we have a processor. So, we have a processor then we need to define an assembly.

This is a little bit how we were would work the the the assembly. Okay, we define this from going from one register to other and we have the arithmetic or the jumps operations. So, this is an assembly. But there is something that's missing here and is how we warranty because how we warranty that we are executing the right program. We We want to have like a ROM.

We have want to have a program and we want to force that we are executing a program because if we see here this is this this are free inputs. You can put any instruction that you want. This is okay. It will fulfill these relationships but how can I create a ROM and execute this program? Okay, but let's move forward and we create this from this assembly we create this we create this table.

So, we we are in code these instructions with with bits. We have in A, in B, in C, in D and we create what we call it a ROM. A ROM at the end is another polynomial where the first instruction, the second instruction, the third instruction, and we encode the all these polynomials. Somehow this is a binary polynomial, we have of the constant the constant value which is wider than address, and we also embed the line with the line of the the line of the program. This is the first line but the line zero, line one, line two, line three, line four, line five, okay?

So, we have a set of values and with this we have a polynomial, okay? We have a polynomial in the ROM. Okay? And we want to guarantee that we are executing this ROM. And how we do that?

With again with a single block up. We're taking all the polynomials that compose the instruction, the address, the set A, set B, jumps, arithmetic, all the the instruction all together. We pack the same way that we did it in the ROM. Instead of having the line in this case, we have the program counter. It's the program counter indicates which line should be executed, and then we just force in the last is that in stress is included in the ROM.

With this condition, we guarantee that we are executing actually uh uh a ROM, okay? So, with this we we can have a ROM that executed that a ROM. So, we will have a processor with a ROM that's executing. And all that defined it with uh polynomial identities with this with this language, okay? Of course the the EVM for building the EVM, the state machine is similar to this but with much more complex.

We have of course in the set of working with 32-bit operations, we're having 256 operations. We need to deal with the gas, we need to deal with the max mem, we need to deal with the stacks, we need to deal with the calls. So, there are some extras because we are tailormading this uh built So, this this processor in order to execute opcodes Ethereum opcodes. So, this is why we are adding these these um you know, fine-tuning things that will help us to implement the the opcodes, but they they are the same. Of course, will be many other state machines like, you know, Keccak, um um um signature verifications, uh comparators.

Well, there is a lot of It's a lot of a lot of state machines, but with these we will create the the full uh Ethereum virtual machine. So, summarize is we have this PIL language. This is like the hardware layer, you know, it's uh we're defining these state machines that work together. We have uh uh with these we define the the the the state machine. We have an assembly, okay?

And with the assembly we create a ROM, which actually has a specific program. And it's a program that actually implements Ethereum. It's actually It's a program that process as an input process many transactions and uh actually and and calculates the new state. Well, actually it's a a a a single process that executes all these, okay? We have an executor that actually is the the runtime that the thing that takes up the transactions and actually creates these uh uh polynomials and then uh with these we generate the STARK.

This is better represented in this next slide, okay? So, we have the executor. The executor generates a proof. Of course, we have we have an an assembly, we have a a ROM, we compile that to an assembly to a you know, and this we we we we plug it to the executor. The executor generates a STARK, okay?

With the PIL language we generate the we compose the STARK and with the PIL language through Circom and all the all the uh the STARK we generate a a circuit to validate the STARK and then this is then at the at the end is verified in Solidity. So, this is the the process is very much uh is very much this. Of course, the prover is not the only The prover is not the only thing that we have to implement. The prover is just a piece of our running of a ZK-EVM. There is also a node with all the node transaction pools and uh so on.

and of course all the smart contracts layer one layer two here if you want to see how we are going to do all the transfers layer one to layer two we have a I did a presentation in Liskon so you can find it in YouTube you can find there and of course we also have this coordinator selector. We have a new protocol we can now improve efficiency probably have some opportunity to explain how it works but this also what gives the centralization but all these pieces what we are building some of who we in in Hermes. And the planning for Hermes of course this is not full commitment this is a project project we are doing is quite challenging but this is the this is the the schedule that we are managing internally. We are very excited right now we are running very fast we have an incredible team right now that's very motivating for doing this. I think we have at least in my eyes we have the best team in the world for creating that.

We are very I'm sure that we are going to get it. We are very really very very very excited and looking forward and hope to scale Ethereum very soon. I don't know if there is any questions but that's all on my side. Thanks so much Jordi. Um there's a couple of common recurring things in the questions which is people want to know how they can learn this on their own pace because there's a lot that happened in this talk and people are curious if they can find it whether it's the copy of your presentation to other links to understanding where you talked about PL.

I will make it copy and everything we are doing is open source so sometimes we are not publishing right now because we are changing very much and it's things like that but we will open very soon as as the pieces get more consolidated and yeah you can check out Polygon Hermes repo and there is a lot of information there. Awesome.