ZK HACK mini - Polynomial Identity Language Workshop

Transcript

let's start so i i want to explain um i would explain one of the tools that we are using to build the zika vm as you know well i'm george velena i'm from polygon hermes and what we are building is a zika vm with a slightly different approach that many other teams we are trying to build uh what we call it a code compatible uh zig area so that means that we want to we want to build you know a proof that actually it takes as an input and state route it takes transactions but these transactions are ethereum transactions you know and as a standard as possible within transactions with rlp with ecdsa

signature with uh you can create a smart contracts called smart contracts um you know there are some gas values so exactly the same that it does ethereum and we are trying to reproduce inside the kdm uh so you decide to do it inside a well insight approver so we want to prove that this new state is uh the one that you get after executing these transactions according to the what we call it but what would be a serious standard this is well has a lot of advantages uh but it's also a little bit challenging because you know the the the avm was not designed for zero knowledge

so there are a lot of things um explicit to the abm that are not that are not as easy to implement inside inside the search with somehow but we are doing and one of the pieces that one of the important pieces that we are doing is is spill just before starting to peel just uh the the strategy that we are following uh from the proof system uh is uh we're we're working with uh we're creating a stark actually we are at this point i can announce that we are moving to the uh to the go to the gold uh to the uh polygon zero uh prime field and we are

using very much technology so this can be a star come here because if you start so we are using all from the proving system everything is in the stark but we actually want this to be verified and changed so and these starks in general are quite expensive to verify in chain so what we are doing is we are trying to create a circuit uh in in plonk or gross 16 that actually verifies this stock so it's a kind of it's a it's a proof of proof it's a it's a girl 16 proof that's proving a stark or if you want a plunk proof that's proving a uh a stark okay uh yeah um just let me just move uh move forward so what's what's feel you know the thing is that uh okay i want to generate this

proof and when we're working with uh when we're working with starks uh the idea is that we want to generate a set of polynomials that have different constraints different identities that needs to fulfill these polynomials and this proof that actually these these transactions are built uh correctly okay but how we how we do that so we need to build these uh you know these polynomials in these relationships between polynomials and this is where pill uh comes uh comes up they okay so uh and the pill is about building mainly it's about building state machines so the the the idea of of building this proof is it's a little bit

different that when we're using a r1cs system in another one cs system we have a circuit where we have signals and then we have relationships between signals they they are the similar to the hardware when we are working with this um with a start system with an ioppt system it's mainly that um you have like a constraint it's like the days are having a clock you know you have a clock so you have a state and you have a relationship between the input and the output and then you you you just clock and you have the same relationship and you are advancing you have a state machine you have a clock okay so that's the the little bit area but in order to design these systems in order to design this hardware we need

that that those toolings we need to build these hardware somehow okay and pill is very much like that it's like it's a tool for building these relationships between um you know between signals with uh with the clocks in order to build these state machines okay so and we are preparing uh we're preparing it to to to generate the proofs so in order for that let's let's start with a single let's start with a simple state machine okay it's a steady machine that we will use it later but this is a very simple steel machine it's a state machine imagine that i want to create a polynomial understand a polynomial for the people that's new and that just understand a polynomial as a set of

values as an array of values okay and and the idea is that we want to generate constraints about these these values we want to generate uh for example okay so this is the the the the app so um a state machine and each value is like a clock you know just that you are evolving somehow so in this state machine what we want to build is mainly um uh we want to build uh numbers of 32 bits so we want to have a polynomial where that has a 32 bit numbers and we want to guarantee that all the numbers in that in in that polynomial are 32 uh bit numbers okay so what's the strategy well we will see that it's quite easy to do this for example with 16 bit numbers

so having a polynomial that and guarantee that uh it's 16 bit numbers we can use block up a broke up technique so we have a relationship in polynomials that's quite easy to guarantee that a polynomial is inside a 16 another polynomial but the 32-bits numbers or 64-bit numbers is is is too huge you cannot have a polynomial with that many values uh you know reasonable sites and you won't have just uh but you want to guarantee that okay so how you do that what they do is you build another polynomial that actually has 32-bit numbers how we do who we build that well we build with uh with mainly with two steps in the in each step we put the less significant bits 16

bits the up significant bits 16 bits so we have like it's like two instructions a set and and accumulate somehow this is the this uh this polynomial here and the idea is that while you see that the three and the seven and we put it so here oh sorry we have this the three and the seven and then you just in the second in the so in the first phase we put the three and the second first we shift and when we set the seven the next we just rest it and put the next one and so on okay so you see here it would be like one register it's a state machine that have one one one one input one output has one one instruction in this case it's a constant instruction if it's set or reset just this is the zero one and then

we have this free input it's just another it's a polynomial it's a register that can be any um any uh 16 16 bits value so how would we write that in in in pill okay because here in peel mainly here we we define um you know it's a constant polynomial here one one one one comment here when you see this u16 bull u16 this is just for packing this is not so all the numbers are field numbers okay but this is just a hint for for packing so when you see this just somehow forget about so forget about this it's not this is not a constraint it's anything it's just for internal or packaging but we it's it's comfortable to put it here when you are defining the

or define the value so we have by 32 this is a polynomial that has all the possible numbers between 0 and 2 to the 16. okay and then here we define this uh this uh what this uh this state machine it's beta4 it's we call it this byte4 okay and here we have a constant that the constant is just uh it's a constant polynomial it's one zero one zero one zero it's the one that we saw here okay this is one zero one zero one zero this is defined okay here um we have a committed polynomial this is freeing this is the input okay this is the one that are 16 bits here in this line here we see that uh friend must be in global by 32 this is this is

the first thing that we see this is a block up so we are actually here is hidden all the polynomial identities that are embedded in block up so this uh when we are generating the proof this in will be replace it with all the uh all the polynomial constraints in order to guarantee that this framework is this inside this uh byte tool okay so we defined also the committed is the with another commuter polynomial which actually is the out is the register that we are evolving and here we define the state transition how it is so the day if it's set is one mainly this is set is one this means that the second term is zero and then we just put three in the odd register

okay if set is zero then this is zero and then we what we put here is okay this is going to be one so here what we put is the odd the old value shifted 16 bits and then we add the the input and the input is 16 bits so the out is going to be always 30 to 32 bits so this is a very simple you see this is a very simple um steam machine in order to build uh just uh 32-bit numbers with this we have the warranty that all will always be 32-bit numbers which one whatever we choose depending on the frame we choose we'll have different values but we have the warranty that all those values are going to be 32 bits

numbers okay so this is the first example okay this let's build like another state machine that's a little bit more complex we call it this arithmetic so imagine that we want to build sets of values each set contains a b c d and e and that fulfills this so at certain point it fulfills this condition that a times b plus c is equal to 2 to the 32 d plus e where a b c d and e are 32 bits numbers so what's the strategy well the strategy is we will have five registers a b c d and e we have a just a well a free input so we can put uh for

input the same this is going to be a 32-bit value it's the same that before and the idea is that we will have like a kind of an instruction so instructions will be just slow them and put the latch so let me go to the so let me so let me well the idea is this here you see that we have maybe in in the first so in this clock we load a so in this clock we load b in this clock we load c we log d we load e and in the last in the last one we just latch with latch means we okay this is the the valid ones the ones that we want to commit the ones that okay this is the the one that will we warranty that when latch is one then a times v plus c is equal to

the e or this is the most significant bit and is the less than key and b okay so how we do that in in pill well we define the uh well these constant polynomials a b c d and e is a b c d and e you see a is one in the in the multiples of of uh uh six uh b is uh one and so on so you see here the construction we we have also the the constant latch okay we have um and then here we start define freeing it's a committed polynomial we define a b c d and e and here is the first thing the first interesting thing that we see we see that freeing must be included in the byte four byte four is

actually is the the last uh the last state machine that we're defending before so with this constraint we guarantee that frame is a 32-bit number okay so it must so the idea is here i can put everything here so that is i can put everything here so i can choose any number but uh must fulfill this so i will have also to go to the base four and generate this number in the other is in the other state in the other state machine okay here i define the state transition for abc and then mainly is when when the set a when when i'm loading a because then i'm putting a and if not i'm just putting the last value the the prime here is the next value it's in the the

language okay and here in the last two lines mainly what we are doing is well we are calculating mulsum which is a times v plus t minus c this must be zero so this must be zero when the latch is is one so this isn't the last in the last uh in the last uh uh so in the last line so when latch is one in order for this to be zero this must be zero well not just zero is going to happen though so that's i don't care which are the values so why while i'm loading a b c and d because this will happen why i put here two lines and i don't put in the same line well here what i'm doing is um one interesting thing for the proof is that i'm just working it is an i had only yellow like

going like doubling the degree in in each time so in this case a times v this i double the degree and but when i'm doing the degree and then i create another polynomial that's a mulsum and then i do the equations on that this is very interesting because this is what uh we don't grow the degree so the thing is that when you're doing the operations you you are you are you are extending the degree you know just you do multiplication you do degree two then you do another multiplication you multiply the degree by four and then you multiply them and you go to the degree by eight and this is this is not good so what we are doing here is we are in the in the prover mainly what we are doing is we are creating what we call it uh like a quotient polynomial that

allows us with committing an extra polynomial with the cost of committing an extra polynomial we can do we can go back to the degree n so we go to the two end but then with this question polynomial will go back to the degree and so at the end what we are trying to do is somehow um have us less polynomials as less committed polynomials we want but when we when we when we extend the degree instead of extended degree what we are doing is just adding more polynomials okay this is more more optimal because you don't need to go everything uh to degree eight uh you only go to another poll you just create another polynomial which is much more expensive

that uh extending all the polynomials that you are using in the system okay so this is the trick and this is where why we are putting this explicitly in the in the in the language okay so we already have uh well here we have uh two examples of two state machines one for creating 32 numbers another that's using this state machine for creating multiplications but actually what we want to build is uh we have state machines we have processors so what we want to build mainly is a kind of a processors will be a very basic uh processor uh so basic basic for processor for processing things so processor will have

check generic resistance here for example is a b c d and e we have a program counter so a processor has a program counter so that's mainly which line are you executing this is the program counter we have an instruction an instruction is represented by a set of uh by a set of uh polynomials so right if you own but they buy a set of flux okay so maybe it's just some one bit would be when one of these points would be a multiplication another if it's a move maybe another if it's a storage right or a memory read or so it should have different instructions maybe it's a jump it's not a jump and so on uh we have we have also a free input and some other uh registers we will see now okay so how we would do it in p well we

define a lot of you know all these polynomials we we do this definition of these polynomials this is just just normal definitions of the polynomials okay here is just um input verification actually we can do it all this actually we are doing with a single block up but this is just a input verification so that it is a binary number for example or that you know sorry by two or whatever it's uh you know maybe it's in by two and address is just in by two so we have different constraints and let's see let's go to the first uh interesting thing imagine that we want to do a move how we would do but this is in a is this is part of the instruction so if you have an instruction where imagine

that we want to move a to c so in this case in a is going to be 1 set c is going to be one and what we are doing here is let's see we are creating this operator this operator is just uh it's a kind of as we're selecting in a and we adding with a in b to wedding b if in b is one we are in c if in c is one so if only in a is one or this is zero so we are just adding a so in this case operator is going to be a and we are just here in a prime we are just putting uh so if set a is uh one then we are putting operator to a uh and in the next in the next round and if not we are just

keeping the old value and this is very much what's saying here if set a is one then this is op a minus a plus a so it's up it's the next the next value of a prime is uh uh is op and if said if set a is zero then the a prime is just a we are just keeping keeping the value so with this we can have uh moves okay maybe there is an instruction and this is cons this part of instruction there is and we can have an instruction for if you're putting a four in d okay so in this case in a and b and c in b is going to be zero const is going to be 4 so we are adding 4 and set b is going to be 1 and so we are putting 4 in 1. so with this we can have instructions for

moving between registers and for inserting values using registers we can have also uh instructions that allows to put any value to a given register okay and this is important because for example when we want to do a multiplication we don't we don't have an instruction we will not have we don't have an instruction in our state machine that's going to do multiplications what we are doing is we are letting the we are letting the the user to put any value to c and then checking that maybe a times v is equal c so this is we are allowing to put any value and then checking later and forcing to check that this is a a multiplication okay of course we can have a conditional

jumps in this case for example we can have an instruction jump f0 okay so here we have a it's a kind of a circuit that's we can detect if it's zero or not this is what's in these uh three lines here so the this is zero is going to be uh is one if operation is zero and zero if if if uh if not okay we do this with this in in in intermediate value in the inverse which is the inverse of the op and then filling this we can we can we we know if if it's zero or not so if it's if the if the input is zero and the jump uh and and the instruction is a jump if zero then we have to jump and then the

program counter will be either so if the jump is one then uh it's going to be a new address so we are going to jump to a different others the problem count is going to go with these values but if jump is zero then we are just going to the current instruction plus one inc is just a normal instruction it's just that just it's just one it's a it's a constant polynomial so we are going to the next instruction okay so we have moved we have uh uh conditional jumps jumps and conditional jumps and and here is the what we will call it before we we have this uh multiplication okay so making our own if you want this added mutation imagine

that we want to do a multiplication okay how we would do it uh well we would put it maybe we want to multiply five times seven okay maybe we want to put uh five in a uh seven in d 35 in c and then we want or 35 in this case is in d and then we want to check we want to check that this is valid how we do we do this uh main dot arrest this is part of the instruction and here we have a block up so this multiplication that i'm assuming is correct in the mainstay machine i'm forcing that this needs to be calculated in the arithmetic state machine that we saw before okay and

these are this is these are selectors that allows just to to do this block up in um you know indeed in some specific uh so in some specific rows in this case in the in the case of the main is only when there is uh an aries an arithmetic or multiplication for example it's arimatic operation okay and the on in the other side in in the where we're doing we are uh taking uh taking as uh you know real values when the latch when we saw in the last uh state machine with latches one so this r is not latched this is uh we saw it here before it is arif dot latch this is what latches one that's actually is when

these values we warranty in this state machine that this value says okay that this is the real multiplication and so on and this is this is very important because you see that we can with this system we can have different state machines we can have different state we can have different state machines and with this block up instruction this we call it in this allows uh allows us to connect one to connect uh you know to connect stained machines uh one each other and this is this is very now this is very interesting because this is what allows us to do engineering we can have a state machine for doing

binary operations we can have a state machine for memory we can have a state machine for storage we can have uh different state machines and we connect them all together with uh uh we connect them all together with this block up okay and we we do it in this in in this one line of code uh somehow okay this is hope would be for example okay we have a processor if you have a processor then we have a kind of an assembly okay so this would be an example of how this assembly would look like okay here when you see the dollar rest dollar array this is the the three inputs you know when you want to the problem is that when you are executing an assembly that means that you are building these trades you are building

these polynomials you need to know well it's a free input it's an instruction that allows me to put anything but uh what actually i have to put okay and this is what i indicate here so this is a free input when there is a dollar here that means that uh what we're putting here is a free input and and this is just um kind of a language just a sub language that allowed that tells to the executor to there's the the one that the executor is the pro the program that's building these uh polynomials it tells the executor what exactly to put okay so in this case for example we're putting result to e and here we're putting a value a we are putting a value b and here well here i'm i'm i'm i'm so

strongly jump if zero then it's okay here what i'm doing here is just i'm just test i i'm just testing that i have like two values i have i have two values that uh i'm testing here in this program i'm testing that that i have two values and when i multiply them together it gives the result okay of course without checking and but it's just it's it's 232 bits numbers so i'm just putting the result to e and you see here the first in general the first instruction is for the publish reserver for the public input okay so we have the result to e then i put it in a value a okay i uh i subtracting one so i'm checking that a is not one and if a is so a plus minus one is zero that means that a is one and

then i'm saying no no that's not okay okay so then i'm just jumping here then i'm putting b i'm checking that b is not one if it's not i'm just jumping that's not okay then i'm putting c to zero d to c and d to zero and then uh here i'm just uh this is a mistake here well i'm just putting e um well i'm just selecting it's just i'm selecting e and no it's not a mistake so i'm just selecting e and here i'm pushing arithmetic so in this case i'm forcing that a times what i'm forcing here is that a times b plus c that's zero is equal to d which is a

it's a number and a time c okay so i'm checking and if it's if it's if this is z if if if it's okay then uh that's fine so it's so it's okay but if it is not okay this i will not be able to generate the proof so this is going to be invalid okay and if it's okay then i'm here i'm just setting everything back to zero because this is a cycle program so i need like to to start over to start over to start over again so but this is an example of uh of this state machine which is a very simple one okay one thing that's important here is okay but what's the what instruction uh so what do i so how

do i know that i'm executing the the right instruction so which program is executing because here i could put uh as an instruction i could put everything you know the this this this polynomial so how i fix all these polynomials that set up the destruction in a and b and c i can put anything there so i need to i need to force that this um this processor is executing a specific specific program it's including each instruction it's a specific problem so how do i do that well what i'm doing is well i'm generating the program here is this program that we saw here before here is the programming assembly and here is the

well the translation to uh uh to this thing in this case for example i allow this is an in-frame is one so i don't put anything number and then set e is is one okay so this is the the program here is any number goes to a in this case is well i'm just putting in a so i'm selecting a here in the constant i put minus one so i i in the in the up is going to be a plus plus one and then here is jump if zero so if the result is up if zero then i'm going to address eight so this is all together this is like another instruction so this is like a set of uh polynomials uh all together okay and well here is the translation between the program and the you know the

represent the all the polynomials that uh represent in this program so okay i can convert this i can convert these uh polynomials to a single polynomial this can be done with uh well actually we are doing now with just with a random number but in this case it's just uh we are this is a field this is a big field so we are just putting the constant the address the line in different places okay so the instructions you know them together so we have a single polynomial where the valuations are these these numbers and then actually what we are doing is okay we are just checking and this is very important but here in the in the important is that in this in the program

we're also putting the line so this is zero one two three four five we're setting the line number here okay and the idea is that the instruction that i'm executing here so is the the the the actual name of the actual polynomial okay when i build this plus the program counter which is the line here is the the less significant part in this case the line here must be in the row okay with the where the rom is this this this value actually all this i can do it with just uh you know because with more instead of having a single drum polynomial i can have like many wrong polynomials and with a single and with a single block up okay but this is the this is the this is data and with this we force that we are executing a

specific program okay so okay so we can know we know how to build uh state machines simple state machines that we know how to build more complex state machines and the well with this we can do uh well we can do a stain machine that's suitable that's tailor made for processing ethereum transactions this is a little bit you know it's the day is the same they then it's the same the time is trading but it's a little bit more complex here for example the registers are not 32 bits numbers are actually are 256 bit numbers so we need uh more registers in this case

uh well this is this this transparencies are a little bit old in this case for example for 156 bit numbers we we are using four chunks of 64 bits actually we are moving to the 64 premium so here instead of having four registers we're having eight registers we are at this point we are adapting all these uh stuff with this neoprene number but the idea is the same we have a state route and we have a lot of things that are quite specific to the to the evm here we have for example we have a gas counter we have a maximum for example for tracking the the memory we have a context so that this allows for example to do calls you know which call is a kind of a context

and when we are processing a call of code then we are doing is we are changing the context uh somehow and we can go back and if there is a throw we can recover the last state and so we have everything that we need in order to process the avm but the idea is is is exactly it's exactly the same it's a little bit more complex more resistance but the idea is very much the same okay so before so before jumping um further so i want to go back here so okay here we have the the polynomial uh identity language and what you need in

order so what's what's what's the requirement to build all these of course you need to build the pill for building the different state machines each pill of course we have some constant polynomials we have also to build those conscious polynomials and the other thing that we need to build is the executor okay the executor mainly is this uh polynomial builder we have a an input each state machine so actually the the state machine of the input will have the transaction so the auto state and the transactions we want to process so we built we need to build all these polynomials that uh we need to build all these polynomials uh uh that will fulfill these uh these uh identities okay but that's it once we have these polynomials built then we can

automatically and it is a process and this is what uh what we have at this point and we are rebuilding for the new prime but what we have at this point is once we have this executor so we have these polynomials already generated then we can actually build automatically uh we have all the tooling for building the the the stark automatically we have also uh with this field we also generate a circum language that actually is the very fire of this stark okay so we generate a silicon language it's a very fire of this type so we can plug this to this start and automatically we generate uh the the the proof and and then we can very validate so in order to build the so

once we have this this this this tool set we have this this this uh of the system the only thing that's required of course is designing the state machines um creating the constants creating the executor and uh that's it once you have the polynomials then you already plug it to the to the to the system in order to build the proof and this can be adapted to any proof uh that will that that we want so any proof that that's validating polynomial uh constraints polynomial identities okay and this is from the pill then you just plot and this in this case where we are plugging into a start generator and in

this case as a gross 16 or plonk generator okay so if you see the the tooling that we have of course we have till which is just the compiler well at the end it's just a parser of this uh language okay just to put it in a nice format um with this we are building the the actually the state machines we have different state machines of different kinds that we are working memory storage you know the different binary operations and so on we have this assembly which is an awesome assembly compiler with this we create the the western compiler we have a specific rom which is actually this rom this actually is the program that's running on top of

this uh of this processor this program is actually is an ethereum interpreter it's an it's it's a program that's reading transactions hushing them checking the signatures um you know removing the gas or removing the the gas having the adding the doing the transfers of the value uh calling uh maybe creating a smart contracts or executing disaster is actually is a it's an ethereum implementation in in this uh in this assembly all together that actually uh interprets these these transactions okay

so we have the rom we have the executor okay the executor of this that actually is okay we have this this this this rom and we and the executor is taking actual transactions and is generating these uh polynomials and with this we generate the start it's the start generator and we also have this peel-to-circle actually is the this silicon this tool that's uh generating the the from the pill generating a silicon it's generating a silicon circuit and then you can plot the result of the of the stark uh the result of the start to this circum and this can of course we have the verified the the solidity the solidity smart contract

that actually validates the uh the glow 16 or the or the plonk okay so this is a little bit the toolset that we are building somehow okay um i want to show we have some time well of course just to finish this part of the just to finish the the the project of course this is a part of the prover all these go together with the note here we have a coordinator selector here we have the proof efficiency that we released that we do we did a post in the in the ether search a couple of weeks ago for uh selecting it's a decentralized way of selecting the of selecting the coordinator of fully

decentralized and very simple and very optimal so on we also were talking about the bridge if anybody interested there is a make at all in this one that's i'm talking hope this the we are bridging between l1 and 2 or even between l2 bridge that's quite very simple strike 4 actually it is i'm following an idea that comes from uh it comes from the original charting on ethereum just between the communication between charts but just before ethereum two just in the it's very much in the beginning so we are recovering some of the ideas there and we are just this inter process communication in their language that's interesting if anyone is interesting can go go and check there and all these just uh generate generating

what's the current status well at this point we are finishing to build we we are we are now maybe we'll have a small delay now because we are switching to these uh we are switching to this uh new prime field uh this will with this we believe that we can increase a lot the efficiency of the prover we can go with uh maybe we can get one or two orders of magnitude faster progress just switching to this polygon zero prime field and all these technology with that we also will get the precaution and everything that plonky to already have in there so we can take profit uh

of all that and uh at this point we are building a test net already so we are we have most of the the state machines done we are building all the the foolproof the start the gross 16 the circuit you know just have all the stacked on we are doing these adaptions on the on the prime field and we hope that maybe in 23 3 of this of this year we can have a set of it's not a commitment of course you know we are working on that and we may find something but the idea is uh day days i i want to go vacations just with the testnet launch and then of course there's a lot about it and going main net let's see three four maybe next year okay this is a little bit the plan

and because we have time i i want to like just before finishing finishing let me draw because i have some other person other slides that are i think are interesting just for the pill i think some some of the extensions that we are building right now that i think are interesting one of those is for example who would do in order to build a plonk uh for example a regular regular plonk see this regular plonk uh this would be this is a standard plonk okay so who would be who would be write a standard plonk in in in peel okay in this case we would have um two committed polynomials say this in c we have uh three um well this constant constraints of course you need to build but these

are the the permutation the copy constraints the the permutation uh polynomials okay this is what uh tells you which which signal is connected with with which okay we have the the door constraints qr core qr the people that's familiar with plong should should know that l1 is the first lagrange polynomial that means only is one at the first and zero at the remains here in the pill we define a public input okay there is one single public input and it's uh a of zero so it's the the first element of zero and here here is a new instruction that we are adding to the pill that's mainly uh how we

connect abc with according to sas b and c so sas b and cs are the connection polynomials and we represent with this here is the gate this is the great uh constraint ql times sake we are to three q times c plus multiplication a times v here you see that i i want to go only one um i don't want to extend so i don't go to extend uh the degree of the polynomial so i define this id that's which is a 10b and so this is always uh and to end uh polynomial and in the last one i just put the public input the initial constraint because mainly i'm saying that uh the first element of a must be public input so

a minus public input times l1 which is one to zero must be zero okay with this and this is so with this if i want to build plonk then i of course i need to build s a as v and c which is the circuit itself okay so i need to build this but here i can use the system to build the start or to build anything of the problem if i want to build uh if i want to build you know custom constraints or anything i can add here you know i can i can create the constraints that i want here so i can generate everything i have also block apps so here i have all the tooling that i need to build like almost everything i

can connect this something for example we are using this prong for example for caca you know it's a circuit with a lot of binary inputs and so on so we can have a plonk a plonk circuit in one side and it's connected to another circuit that actually is more like a processor that's just calculating cacs in one side and i can connect both worlds very much automatically on the other uh well just other things that i want to mention is uh well

let me just move it here permutation checks you know instead of here instead of is we can instead of in i can have is just if i want to not to do a full block up i just want to do a permutation check which is something that's thing and this permutation checks is very interesting because i can do it maybe with uh this isn't something that we are adding is uh with polynomials of different degree you know i can have for example a state machine with one degree maybe a two to twenty eight another another state machine with uh two to twenty three and then just uh do a do a a a permutation check but cross domain uh

permutation check so just i can and this is very important because this allows us for example to do some state machines that are quite intensive and work with bigger polynomials and some other state machines that are uh smaller maybe with more polynomials that uh uh you know they don't need that quantity and this allows us to plot plot them to plot them together you know and just some specific computations some intensive computations in one in some polynomials this is also another huge optimization that we can we cannot uh with uh with uh with the system okay so this is very much what i wanted to show let me see if no there are questions i don't i'm sure

that i'm just uh let me see i don't know if you have questions i don't know if i'm in time not in time 30. you go go to the game um confessions chat q a there's the chat session i see the session q a it's sort of just a tear below it uh 12 to 5 47 leave no it is not no if you go on that where the chat is so maybe i think you might need to expand your chat

there should be a little arrow up in the top right corner no this is not oh yeah yeah okay i see it here you found it i think if you go back i mean i think the questions for this session started with anonymous 33-minute uh but this is on sliding this is what i see here is just one hour ago no so it was from yeah so it would be anonymous so the question would be in the example on slide eight is writing free id in global byte two needed this is very specific where is uh the this is the words

okay um the q a i'm in the queue i'm i mean i'm in the chat and then i am in the q a yeah great like like this do you see the latest okay so yes there we go if you scroll down a little bit to 30 minutes ago the first question applied to you but that seemed very specific to the slide so no but this is i the last one that i see is just one hour ago the first one can you explain a bit more about mercury optimization i think this is the last session that's way oh that's the very one for the last session oh okay okay they are they are inverted okay yes

exactly the first one is it is the beginning okay okay 34 minutes ago okay um you seen the example on the slide eight is writing free id in global way to need it as a free id is no yeah what is yes it's needed because uh when you see uh u16 this uh u16 u32 this is not a constraint at all this is just for uh packaging um this is we could we could remove that and probably it's better to remove and maybe for this presentation to be better to remove but for us it's very comfortable to say that this is going to be a 32-bit element because then i can pack them in a smaller uh file uh somehow so i'm just and also

give you some checks but it's not it's not a constraint it's not a polynomial constraint polynomial stream must be defined as it's not saying u32 or saying u3 it's just a formatting it's just a hint it's like this this polynomial is going to be this way so forget about this youth 16 u32 as a this is not a constraint at all we are here let me mention this is we are as you see we are evolving this language and we are working hard and we are changing a lot of things there so that's a little bit the reason why we are not publishing yet because it's like we want to we are adapting we are changing at this point this is very much for it's a tooling that's we are doing to build

ourselves uh you know to build all these kvm it's a very spec it's a tool for very much for ourselves but i hope that at some point we can it's going to be more stable and we can release it and you can you can use it as as you want that's a starkey already support recursion this is maybe i know this is one hour ago sorry uh oh yeah yeah they need to sorry i say i need to go up upwards i'm going downwards that's the the way i'm using how does performance depend on the maximum polynomial degree yeah well it's uh it's quite linear so uh at the end um in the starks mainly what you need to do you need to expand those polynomials that means doing a

reverse fft and then an fft that's uh maybe two two times four times or so on so you have bigger polynomials this fft is going to be bigger and then you will need to mark the lights of those polynomials and their colliding if you have a bigger polynomial the mercurization process is going to be big so that's why you want to work always with small pollen with small polynomials and the scaling is quite linear the bigger double degree double time that's generally is quite very much that fftc is same lock-in but yeah that's very much a rough idea the example

3d well this is what i'm ready that's a stark i'm sorry sorry sorry sorry i think there was a question here why did you choose to implement an evm interpreter rather than a compiler from evm code to a circuit um from dara 31 minutes ago yeah well the ibm is dbm is you know it's quite complex and uh with this we interpret so each of code imagine for example uh a call you know we don't we cannot put a call in a single instruction what we are doing is we are doing like a program that's actually uh interpreting the call and this gives us a lot of flexibility because you know you'd want to do an exponentiation but

you can do actually you can do a loop even for example at this point we are considering to do the the cdsa as a normal you know as an as as a program somehow so we can mix um script somehow so was a set of uh op codes in order to run a specific program but it's not only an up code it's interpreting everything sometimes you need to add a value to the state maybe sometimes you need to roll back and throw here for example there is um well there is a lot of uh you know the ibm is fully of tricks and and details uh you know the stack for example it's like the limit in the stack

memories you need to take in account the quantity of memory you are using in order to compute the gas um you know you want to do there are different operations and we cannot stick to one of code one uh one ethereum of code to one evm of code so an ibm is just a machine that's stellar made so we if we need to define specific codes for doing specific things we do it actually we are putting some registers some specific resistance some specific operations that are very good for that for example well there are details of it but there is one detail for example is about uh you know it's possible so it's possible imagine a transaction

that's uh and saps in a loop or or is using a resource that you don't have enough resources inside your prover that inside your approver so that you cannot build a valid proof but you want to force you want to execute those transactions so we need to have a kind of a contours of uh usages uh accounting of the usages that you are doing in the resources so that at least maybe an uh uh there are some transactions that you just process but maybe an op process but you you you move for you pro you move forward you prove that this transaction is is not valid okay but you you want to build the proof it's not uh it's not enough saying that you cannot

build a proof because then you stop the robot so that's the that's one of the some of the tricks that you need when you need to think when you're building the the the avm how does performance oh no yes this is um that spill basically converts the avm from a a stack based vm into a resistor based bm if noko does each instruction uh connect it's more to a stack push button no a push or a pop is just an instruction and actually what we are doing is we are uh um interpreting this push so the push that who how we put the push that pushes in memory okay and the days when you do a push is uh well when you want to

process so you get an op code we we need to first like the code this op code we have like a special instruction for the coding of course you cannot do if this is so cool go jump here if you just you know you have a mapping a jump table uh for the upcoming so we have a jump table to this to the push and then in the push actually what uh if it's a push of a specific value then we parse this we put this value in the register and then we copy this register to uh some place in the memory and maybe we we increment the stack pointer and maybe we check that this stack pointer is not more than one hundred one thousand one thousand twenty four and if it's more than two thousand twenty four we jump to some throw somewhere in the space but we are

interpreting so each we we do some calculus that more or less more in average and this is depending on the instruction but the idea is that one instruction should be an average of uh between eight and 16 rom let's put it around 10 um codes in average and this is of course this can depending on destruction maybe a call is much more okay but a push maybe it's like four or five instructions in the middle well you know uh and that well again we are popping from the stack uh so that mainly it's reading from memory the point we're gonna start decrementing the stack pointer putting the memory doing the

operation and then adding to the stack so these are maybe a five six uh uh operations and and and so on in there as a totally we are not doing for example multiplications in the mainstream machine we are just assuming that this is valid and then this is with block up we have a just a state machine where we are doing all the arithmetic there's many multiplications uh in there and then with block up we will plug them together the temple proof can be generated in the browser uh not at this point but it should not be difficult to do actually the way we are building is i'm we are building a lot of uh

kind of test code in in javascript and so on and then all the final code is in c plus plus and maybe at some point in brass but it's like the production code and but for testing and so it's in javascript so maybe this test code could be at some point be ported to browser but it's not we are not thinking about that at this point is there some documentation about piro yes if you order polygoner mess there there is a link where i there is a full documentation that's already public and you can check on that if somebody on the somebody on the team is listening they

maybe they can share the link somewhere in twitter or somewhere [Music] no i mean a nat code needs to pop two values from the stack and push the zoom result back to the stack the two pops and one push aren't reflected in the pill just shown as a friend uh yes so actually it's yes you're right but you know when you is what i explained when you have a nat so the ad will jump to a specific uh assembly code you know where it's a procedure in the assembly code and what

will do this assembly code actually we'll we'll fetch the first the first number from the stack but the stack is in memory you know the stack is some place in the memory we have the stacks there so it's going to be some memory read there then we will do the memory read of the second one and of course decrementing the stack pointer okay so once we have these two numbers in the register we will do actually the operation maybe with the native uh method we will put the result uh we will put the result in the frame okay in the result we will put the arif the arithmetic uh uh instructions so that we wouldn't see that this frame that we just put there is exactly so it's

exactly the addition of the other two numbers so that the the the this is number and then this number that we just free in there we will write back to the stack or whatever break back to memory and increment increment the the stack pointer the sec point that we're implementing is non-traditional uh stacks uh in memory and we have to do it this in memory in among other things because you know for example you know in ethereum in you have many when you have many calls each call have has like their own state their own stack so you need to keep tray you need to keep trace of the uh of that so

a smart contract calls another contract this is controller has a new stack so and so you have uh this case is the context we have different contacts and that means are different patches in memory and then you access one one place or or the other okay did you get the question about the bool the booleans yeah this is the you know the booleans and the u16s and u32s this is not any constraint at all this is just a hint for how to pack in order to teach the the executor and [Music] anybody that's using pill how to pack it's insane you can if it's a boolean you can pack this as a single

bit you have the warranty that's going to be single b but it's not uh it's not a cryptographic constraint it's not a constraint at all it's just a way of working it's just uh i mean the hint indicating that this should be uh interesting but it's not it's not a constraint at all cool well one of the interesting things of the pill is that we hope that this will help a lot in the auditing processes so in the editing process you should mainly audit the the maybe you should audit the the pill you'll need the pill that means that of course you need to trust of course the compiler and the tooling that's uh in there but a

specific program just auditing the pill should be quite enough because the pill is the specification of the of the constraints and you want to fulfill okay so this is this is the most important problem you will need more a lot of things more but this is the most important and we hope that this spin language will help a lot in the auditing process