L15 - The Boojum Proving System | by Oles | BlocSoc Lecture Series

Transcript

so as I said before my name is Ls I'm a PL protography engineer and today we will talk about buum so yeah let's start uh first of all uh let's talk about proing system itself how are we going if we want to create some proof system what we are going to do like what uh questions we should answer and figure out to deal with them first of all it's what we are going to prove yeah so maybe I want to prove that I know some prate of hash or I know like some root of the polinomial or whatever and

uh the second one is quite more difficult is how I'm going to prove it so these two parts are also like a trade-off between them because if I want to prove more it's going to be more difficult to prove it in sense uh maybe it will require more difficult technology or just it would be harder to prove and verify in like computational resources so yeah uh today we will talk about uh plish arithmetization so it's a method that explains uh like uh methodology how we can do it and uh you need just to choose

your arithmetization and then uh how some specific format we will talk about it like on the next slide and then you can choose some polinomial commitment and prove it so there are different pols commitment for example we were using uh kcg before buum uh now we using fry there also some other commitments like IPA on which like kind of bulletproof and um yes there are still different research uh research like papers uh discussing new techniques so for now we

stick with fry and uh we are not going to talk about poal commitments we mostly going to talk about arithmetization more interesting it I would say more engineering part because poal commitments are mostly about math and rization it's something uh not so hard to understand and uh quite interesting so what is bu mathematization uh it's like blanish arithmetization uh how it works uh first of all we need a execution trace or just a table that show on the right so it's something like you know like Excel table which has it height uh height and wh and uh we put

like there are a lot of cells and we put some numbers there and then we are going to prove some relations between those numbers and the relations we are going to prove uh you can see on the left side it's Gates look up argument and copy permutation argument so couple of things um uh I also want to mention uh all elements all numbers would be field elements it's uh because we really want to deal with field not with some like real numbers or integers or whatever uh because field has Prime field so just neighbers numbers model some uh prime

number have a really good set of properties and uh they also always bounded so if you multiply different integers you can uh get in the result really big integer but uh Prime field uh doesn't have such problems and uh also there are different trade-offs between uh he at White of this table so we use something like 240 uh colum and two to the power 20 rows and uh how to choose those numbers is uh kind of questions but actually you can use any number the only requirement

is that the number of rows should be a power of two because to make your proofs just efficient because we want to use ft fft in order to accelerate uh like uh polinomial interpolation okay just a quick check if uh yeah everyone okay there's no problem that I should add anyone okay just in case okay so let's continue yeah so the head should be a power of two also uh you want to keep your white as uh small as possible just

because uh your proof and your proving verification will grow linear linear with number of uh uh columns and it grows uh like your verification rows only logarithmic in the number of rows because of and if you talk about like okay it depends on the polinomial commitment scheme but overall like more rows is better than more columns also you have some uh bounds of number of uh rows and columns but it's like details I don't want to keep it to

like uh complex in this part let's move on but uh if you have some additional questions you could ask uh right so you mentioned that uh the WID has to be as small as possible so um currently in the slide you have mentioned a WID of 240 so like is that the standard WID or um like what we do you usually use in production for writing her GS uh yeah why we need the yeah so it's better to make it as small as possible yeah but why we need at least like 240 it's uh because of um let me think because of some gates

we will move to the gates so some gates are very wide so one gate is some polinomial uh equation which uh is like use only cells on one raow and if you have some really wide Gates so gate you need like to have a lot of columns I will also mention it when we will talk about Gates okay sure okay so first argument is copy permutation argument uh what is this argument is about so we have two types of columns we have variables and weakness also quick

small reminder then in uh uh zero knowledge we use a lot of word witness and uh like even in my team like witness can have like at least I guess three meanings at least two so when we talk about witness I want to specify what currently we are talking about witness columns and when I say witness column we just uh says that it's like some columns uh which we use without copy permutation argument so what is copy permutation argument copy permutation argument allows you just to prove equality of different cells so for example in the picture on the right you

can like see two green cells and three red and copy permutation argument allows you to prove that both green cells have the same uh volue inside and the same about Tre so three L red cells contain the same number also like it doesn't depend you can divide uh your cells into different groups and uh prove the quality of like the the cells in one group have the same value uh it's the main idea why we need it it's uh you know to connect different cells so

we use some number for example we in the some upper rows okay we compute some hash and then we want to reuse the hash in some further computations so we need to get it from top and put it to the bottom and then we need to like R quality of those cells and uh yeah witness columns uh and uh complexity does not depend actually on what sets you have and how many sets it just depends of number of your columns that you want to make it them variable columns and witness doesn't have like this property so each cell is unique and uh it's related to some other cells only by

Gates and look up in order to prove it we have like a grand product like this uh if you want to know more why it actually has this like shape uh just it's well described in just the original uh plon article it's not like too hard so yeah you can just uh search there for more information but I don't want to explain uh it will take quite a lot of time to explain why it actually works okay so let's move on then we have Gates what is uh gate is just uh some polinomial

equation that uh takes like some like some polinomial equals to zero and uh what we have here like this equation should just takes take some cells on one raw as arguments and like evalate some polinomial of these cells and we prove that this polinomial equals to zero so for example the simplest gate it's we call it BL check so for example imagine you have a cell and you want to prove that this cell is aen so that it's either zero or one why we need this

check because we usually like want to use some like beats in our VM or yeah just we want to prove that some number is actually a bit and uh then uh how we can like but we don't want say okay it's one or zero we just want to check that it's is one or zero so then uh we can make the following U uh gate x^2 - x = 0 on some cell then uh what we have uh that this number in this cell if we raate it to the second power it would be still equal to itself yeah and it's easy to see that only zero

and one satisfies uh this property um gate has different parameters so first of all like it's number of variables number of weakness and number of constants uh you can see it on the right side uh so number of variables and number of witness it's like number of columns we should uh apply we should take so or number of cells yeah because we remember that we apply gate only on one row so uh in this case we have one variable and zero Witnesses why because it make no sense right to prove like bulling check on

some witness because if we have like witness it will it's it will be hard to connect it to some other cells on with some other Gates and uh like uh honestly speaking we almost never use witness columns because yeah they make proving verification quite cheaper because we don't need like that uh copy permutation argument but actually it makes things much more difficult and harder to deal with so usually we use variables variable columns almost everywhere and what is constant also we have some

constant columns it's just other columns but they're like hardcoded so the prover and the verifier everybody knows uh what are like Wes in this columns for example um if uh we compute some hash function you and there are some constant parameters of that hash function you can just put them into the constant columns to use them because you know uh we use constant columns for numbers that are not going to change from one circuit to another circuit right uh so for one for one L1 block to other L1 block and also we have like

some other characteristics that says a constraint degree and the quotient term so what is constraint degree Dee is just power of this polinomial and what is quotient ter it's yeah so I said that one gate is one polinomial but actually the truth would be like one gate is a set of polinomial so because um sometimes we want to for example we have a gate called compute hash yeah like U posidon two hash it's one gate but

actually uh what it actually do it just it's quite a hard to put uh such big um number of computation into one gate because then we will have um very high degree of that polinomial and we have our constrain degree is also bounded so instead we it into instead having one like huge polinomial of degree I don't know like 100 we will split it into some set of smaller polinomial and uh then it's like we will we'll call those pols like portion terms

and we just group them together into one gate because yeah it's just uh hey uh like before we move forward I just had a a question real quick um my question was what's the point of having the witness column in the first place um you said that it's much cheaper to just use the permutation copy argument and I'm guessing it does not affect the proof in any significant way yeah we want to use witness when it's like okay a very good example okay I can give you a very good example on the next slide I think uh which will show like The Power of weakness but but uh usually they like

they're always cheaper but too uncomfortable yeah when it's like cheaper and it's okay to use them we use them but usually like they cheaper but then like we need to sacrifice really a lot and uh won't righty like yeah circuit so efficiently so yeah let's just move to okay yeah here we have like posidon to gate so sorry what it actually does it just uh uh compute one uh hash actually it's Compu round function of a hash so you have input like 12 variables you have

output 12 variables uh because it's like configuration of our hash and then you have a lot of intermediate values right so these intermediate values you not going to use them anywhere because you're interested only in the input 12 input variables and like 12 input cells and 12 output cells so actually you can use witness columns for all the like intermediate uh thing for example some linear combination raising to the S power whatever uh and the key is okay if your circuit is is

mostly about Computing a hash but they don't do hash uh then it will be you can benefit really a lot from for using this witness yeah because you can make this intermediate result witness and okay you you like it's a lot of cheaper but if you use like uh let's say bu allocator like some other uh Gates that doesn't have some like inter mediate values are much simpler so we you cannot benefit from witness columns great thanks

okay uh so yeah the thing is we also have like uh limit on Max constraint degree and yeah we'll talk about it and now uh I want to talk how so now everything is like quite good you just take some uh cells and you can make uh some polinomial equation if they on one raw uh what's next and uh how we can efficiently place these gates in our table Yeah to make it more efficient so

we have general purpose columns I don't know why there is one over here don't matter and specialized columns so what is the difference the key point is that actually how our proving system works you don't uh just take some for example first second and fourth cell of the first raw and uh it doesn't really just apply some gate to those cells actually you apply some gate to all columns so for example if we use bulling check on

the first cell so the first cell the first row the First Column right so the whole First Column would be like constrained to be bulling because uh yeah we don't put it just so we do this constraint for also column and uh yeah it's uh how specializ columns works so for example you have some red constraint and you want to put it and then it will like be duplicated for all the rows uh but it's not always the case how we want to deal with those constraints usually we need like uh constraint to

use it just a couple of times so how can we fix it it then no okay it's not but actually what we can do is multiply by some selector column so it would be so you can imagine here that we have x^2 - x then we multiply this gate time some bullin selector Let's uh do like this yes some B selector and it equals to zero where bu selector is some constant column it's also an example of constant column so what we have in this case okay if bullin

selector if is zero then the constraint is always satisfied and if uh it's equal for example to one then you actually need to the gate equal to zero I think it's quite complex so I'll try to write it then I use just some pan or whatever okay let's quick note so you just do like x squ - x times some uh bu selector right and it equals to zero so

in this case bull selector would be also a column but a constant column so it could be either usually it's either zero or one so Z or one and you can see that it's if it's zero then uh like this gate is like already satisfied but if it's one then we actually will require that x^2 - x equal Z so using such constant selector additional column we could activate or deactivate some

gates and uh it actually what allow us to do like general purpose columns so what actually happens here is like on each row we can uh activate some specific gate for for example on the first row the Green Gate is activated on the second row the blue gate is activated and then again green and then again red okay any questions it's quite complex part of the presentation um uh yeah I wanted to ask about like uh we can we add more

selectors uh other than only two woan selector columns in uh the general purpose or the speci specialized TNS uh okay if I understand you correctly uh the question uh yeah so for actually you can uh like uh you know the only boundary here fantasy so you can like really think about really complex structures and make a difference of gates and activated deactivate them but uh here's also a tradeoff the simpler it is uh the easier it's going to be to prove so for now how it is uh

constructed you have like a set of gates and you say Okay I want to make this set of gates uh like uh I want to put them into general purpose columns so for example we have like 100 general purpose columns and we have multiple Gates then for each gate there will be one selector which could activate this particular gate on this row and deactivate all others ones yeah okay I got okay thanks and uh the key point that maybe you say okay maybe it will be more efficient for example to you know

like put this one maybe we can fit you know like here we have a little bit more space so maybe we can put some more gates it could be more efficient yeah it will be more efficient in a sense that we uh like use our space more efficiently yeah but it will be harder to prove and to verify because then for one draw for one gate you need like multiple selectors where you want yeah so and we have if we use for example on this R we use Red Gate okay we can like uh put maximum red gates as many as red

gates as we can fit in this R we put them and we activate them all and uh the same for example here we can fit like four red gates into one raow or two green one or one blue uh yeah usually our gate are general purpose but there are some gates that to we make specialized because uh when you use general purpose gate you also need to add like this selector column and it's quite costly and uh also even if you don't want to activate it almost nowhere you always like make some computation in case it's like activated

so uh for example like bin check it requires only one column and we have quite a lot of buing checks so we move to specialized row because uh we are sure that we could fit like a lot but in the other case is if for example you have one gate that is going to be called like going to be used a couple of times maybe 10 maybe 12 it doesn't make sense to make it specialized because otherwise it like require you know like all columns that are going to be used in this specialized gaze are going to be like uh just waste it because you just

call it use like couple of upper rows but you don't need the other ones okay and uh B yeah also you can possibility which we added but almost never use you can bound gate so for example here you can now like make this placement why it's could be more efficient because in uh this case you have some free space yeah and uh green columns you always uh as I said before you for example let uh let's

say that Green Gate require you like four cells okay so in uh the left example uh you you will have like eight columns for Green Gate because there are two Green Gates and then you need to repeat the gate twice but in the right example you need to repeat it only once you just activate it more with its selector so actually as I have said before actually we don't activate like we don't put some gate on some cells we put them on columns and in the left side

we will like have eight columns and on the right side we will have four columns so that makes like Green Gate twice cheaper but it's in case we have like quite a lot of space okay any questions fine and uh just a quick overview what Gates you added you can always like add some custom Gates you want if you want to a bit ride buum uh you can even find the folder Gates and find all Gates there but uh what Gates we use is bll allocator it's

bll check x^2 - x = 0 also it's constant allocator when you want to prove that some cell is actually a constant some some specific constant so uh it will have like uh form like uh x - C = 0 where X would be a like variable column and C would be a constant column that's how you can put some constant into VAR aable column and then prove that it's like placed in a lot of different uh places then we have conditional

select conditional select it's a quite cool gate the right to you and it's like um a times uh B small a um okay let's X time y plus uh Z * 1us y equals for example K or minus K = 0 but let's write it in this form like

say equivalent but this one will be easy easier to understand yeah and also you most likely won't to say that X oh y squared minus y is equal to Z yeah so why is called conditional select because it actually make a selection so here what first gate says lator that Y is actually either one or zero so it's like a bit and then the second gate actually says okay if Y is 1 let K be equal to X if Y is zero let K be equal to Z so you can see if Y is zero then we have like x

* 0 which is 0 plus Z is equal to K so Z is equal to K but if Y is 1 then 1 - Y is 0 and this zero and we have X x equal to K so here we select K would be either equal to X or Z is like depends on why so it's like conditional select one of the most popular and interesting uh gate so conditional swap is quite similar just if Y is for example why you swap the variables yeah like you do like this if it's zero swap

it one uh conditional zero checks the same if some flag is set we check that it's zero also like parallel selection is just optimization of conditional select when we have like multiple of x and z variants but we W use one like Y flag for them and uh so on like these Gates on the left are just some basic ones that most likely you will need like a lot just because uh you want to to just because you want to do some you know like logical

operations uh and the gates on the left are more specific for our implementation so as far as we want to uh do some like uh computation some virtual machine computation we have some specialized uh gates for for example 32bit arithmetic so we have f ma is field okay M and A is multiplication and addition and F I forgot what does mean f but yeah it actually something like x * y + z equals the result just some GES

that make a multiplication of C2 numbers so actually yeah and then like one like the number inside is like you constraint that it's like has 32 beats and then you perform some like addition and uh yeah some not just usual field Edition model or some prime number but 32 be with like carry beat and so on or multiplic ation and this just because we want to implement some virtual machine computation and also we have uh something that like matrix

multiplication gate seven power gate and posidon and posidon 2 so these uh Gates just for computing the posidon to hash and uh usually we just can use theid to Hash but what is the problem we have like some fixed whes of our table yeah we don't want to make it too big then if like we have like quite a lot of hash computation we can put posidon to gate but uh it makes uh computation of hash function more efficient but on the same uh time it requires like a lot of

space it is really we can really benefit like when we do for example some recursion when we want to prove that we verified some other proofs because we have fry we need to like compute a lot of Mark Roots right uh like if you're familiar with not just uh you can know that uh in order to verify fry we need a lot of hashes so that's why okay then posidon to gate will be efficient but what if we like have quite a lot of hash computation but for example the most of the circuit is about lups yeah for example there is circuit that not uh POs

to but for example there is precompile for chak or sh 56 has function special circuit that uh comput this has functions for virtual machine then we have like a lot of bat operation yeah most of this Circ there some beat operations also require a lot of lookups which allow us to do beat operation more efficiently and so on but uh we need to compute hash like not so much and our columns if we have like 240 columns like maybe 200 of them you know approximately I don't remember the exact numbers but really huge number of them would be just busy with look up argument not with

Gates and then we cannot like in the remaining columns we cannot fit posidon to gate because posidon to gate is very wide it's like 150 150 cells so 150 columns and uh in this case also that's the reason why we are going to use like at least 240 whatever like why we need quite a lot of columns just to allow posidon to gate and some lookups and uh yeah so when it's not efficient to use posidon 2 we use seven power gate we just it's just you know x to the

power of 7us y = 0 so Y is actually equal to the S power of X and matrix multiplication if you like we need to do it it's just linear part of like posidon to round function yeah okay any questions about our gates okay so I was just wondering so how computationally complex can gate be um you can use as many variables as you want they should just be placed in

one Raw and the maximum degree of your polinomial or one polinomial uh is like seven or eight it like if you use general purpose columns it's seven because you also need to add selector which will increase the degree on one and if you want to use specialize columns it's eight use degree eight right uh so yeah this is only limitation and then it could be like as big as you want but purly if if it's bigger it's harder to prove and it's harder to verify okay got it okay so uh look up

argument uh look up argument just a tool that uh there are different operations like uh okay when there are like operations that are easily expressed with pols for example check the ballen conditional select that I have showed you also like just field multiplication feel addition yeah a plus B minus C equals z it means that c is the sum of A and B but uh think about you want to sore two numbers okay you have one 16bit number second 16bit number you want to sour them uh you can do it

also with Gates but uh the idea would be like to split each number into bits then sore bits like 16 par ofits then again concatenated the number it would be like uh quite hard instead we can use uh lookup argument so what is lookup argument is what what is lookup table so imagine you have like some precomputed table uh usually we use like three row uh three columns right so you have table and uh you can which uh like there could be like yeah triples of numbers and you

put them all triples that are like let's say good for example you can make a sort table it will be like uh of we use like sort table of bytes so you the First Column is some set of bytes uh like the First Column is different byes the second column is different bytes yeah and you just take the like all pair of bytes and the third column would be uh equal to the sore of the first and the second one so in this case you need like 2 to the^ 16 of rows because like first argument have two to the power eight

variance because a bite the second one have two to the power eight variant so in total you have two to the power 16 cases of all possible pairs of bites and the third column would contain the sore result of them or you can also make and or or or whatever and uh then when you want to sort two bytes you don't need actually to do some uh complex stuff you need just uh to prove that this triple of numbers actually in exists somewhere in this table in this uh in the same time you

don't actually reveal what where it is located You just prove that it's located somewhere in this specific table so when we want to sore two bytes we can just prove okay that it's located in theor table these three numbers locates table that means that actually of the first and second equal to the third uh and yeah so we have multiple tables that contain let's say three rows actually uh you can use like wider tables usually we use uh three or four but uh like okay we use three or four but usually we use three because uh some

beat operations or some uncomfortable information uh operations just like uh okay we have two arguments two inputs and one output and yeah that's it uh then um yeah so how can we how can we choose between these tables we can add one more row so make it four or five in total and the last row will tell us the table ID so we put the first table here like and then table ID would be like zero and then the oh or one and the table two and here we have one so then when you want to prove that like three numbers is

exore you need to put like these three numbers in one row for example this copy permutation argument then you want to put some either constant or some other type of cell uh to like show the table ID and you like somehow constraint okay let it be umor table ID of sor table and then you Pro that this four numbers is actually located in the big aggregated table so table AB will just show what small subtable you're going to use um the formula on the right is just if you want to get know more about Mass

behind Lookout tables there is an article CQ I guess if you have will have some questions out the lecture you can always write kogan because I'm not in the chat and he will add it to the chat I will share like all the links you're interested in and yeah whatever um okay any questions I don't understand how the complexity of calculating those values again is greater than proving that they exist in the table uh it depends on like how more how much do we save when we use table

instead of gate right I'm sorry can you please repeat yeah like the question is how much we save when we use table instead of gate right like oh yes right okay it actually depends of the table some tables so yeah but uh you can try uh there is uh cool article I guess yeah I think I should uh find and send you one article if you're interested intiation it's about different time of arithmetization it's

like I would say it's completely different that what we're talking about but it will give you like idea how to deal with some bit operation when you deal with uh on the gates without look up tables for example uh let's uh try to compute if we have like X you want to do sore y right where X and Y abides X or Y equals to Z so in order to do it with usual uh Gates first of all we need uh to add uh some variables like X One X2 which will stand for the Beats

of x x 8 and the same for y so and the y1 and so on and for each of this bit we should make U um what we should make we should make a bling check so we also should like add 16 constraints of Type X like x i squared minus x i equals to zero so we have at least like 16 these constraints for x and uh for X bits and

Y bits uh then we want to S them so we want to make something like that y equal um I don't remember how to sore but okay and and make end is simple you just multiply and it will be like making ant rightor a little bit complex but I don't know to spend time on remembering how to do s but it's also like uh not too hard yeah just equations that like du s for bit is actually simple like andt and whatever and uh then you also need like eight those

Gates so eight those uh 16 Z and then in the end you need to do something like okay Z equals z like 1 + 2 * Z 2 plus uh 4 * Z3 and so on yeah to sum all the bits and you need to do this equation actually three times because you need to do it for that then for x and for y so in total you get uh 3 + 8 + 16 it's 27 additional

Gates and also you got uh like 16 additional variables so they also should be like they also like spend your uh space in this table because more variables more space and uh this uh how it's happened with logical bite tables but uh yeah so other would be like you can compute kind of similar way oh I was just wondering uh why are we running the Boolean check on every bit of X and

Y why we need Boolean check on every X and Y yeah okay because in other case for example you can okay so in order to split we need to use uh this uh equation do you agree then like if for example let's assume that that is equal to two in this case we want like z z z one equal to zero and Z do equal to one yeah like bits right

and that three equals to zero and so on and all zeros but uh and what you can actually do you can do like this let put like two here and zero here so the first bit would be like two okay it's not possible but it will satisfy this equation so we actually need also to prove that each of these numbers is is one or zero okay thanks mhm yeah and in fact that you don't need to check it for Z because z y is like multiplication of X and Y so

it it's going to be always like zero or one and so you can save like eight constraints to not checking that it's okay so let's check if I miss something in the chat okay great uh okay and so almost over okay let's just quickly yeah quickly continue and we have yeah so last couple of uh slides like make it um so yeah we can have different

configurations in our circuit first of all we have can have no look up when we don't want to use any look look up we can have table ID as variable uh so what does it mean like uh so the table ID here it could either be variable or constant uh why does it matter because if you use table ID as a constant column you it's very like simple okay the first Like You can predict how many range checks you want how many like uh oh not R checks but uh like Source how many like ORS and ends and what

operations you're going to have when you like put table ID in the column as a constant but maybe you want to make it a variable variable would be more flexible but we also almost never use it because uh it's uh it's uh it was like an experiment should we like uh try to optimize something using table ideas variable but actually it just requires it's not so simple to optimize something and actually it's even worse so usually yeah we just used table ID as constant so also we you have a white of the table as

I said it's like three or four usually we use three uh yeah I'll show you the list of tables here what we use and what we also have is we have share table ID so imagine you have like a lot of columns follow C tables so three columns and other three columns and other three columns other three columns yeah and for each column for each three column you also want to add a table ID to recognize to what uh like um what table you should apply to this like three cells but actually you can say Okay I want you know like a lot

of uh lookup column but I want only one a table ID in this case uh all your lookup column will share one table ID and it means that like on one raw only one lookup table would be available so here lookup ID is very similar how we work with gate selectors in Gates right so table ad will just activate you some specific lookup table and you can either go with one table ID for all like we did in general purpose columns or you can say Okay I want like something specific whatever and uh also you can uh use specialized columns

or you can use general purpose columns so you can also add look up to the general purpose column we discussed here so it will be like usual gate and also you will add here look up Gates but usually we just move Look up to specialized and keep look up and Gates separately um yeah and in this case you will have like whites how many you oh no no no no no number of repetitions sorry number of repetition so how many you want to yeah repetitions it's quite similar as we have here number of repetitions of special column

when use Gates yeah number of repetition and share constant is quite similar to share table ID okay and the like what tables do we have it's like 8bit an table 8bit Bob table like it will just uh you put two arguments then you receive and or like and or and S concatenated so then you can split and like separate the end result the or result and theor result also it's a 4bit Sor but s of three

elements so it's this one like four b s of three elements is an example of a table where we have like four elements so here it will be like three three inputs and one output we use it for like also for tables for sh 256 so I most likely need to move like this to the right or whatever we have bite split table so what is by by split table uh when you have like 16 bit number and you want to split it to two bytes or instead you want like to conate two bytes to one uh 16bit number then we have like

three numbers whatever like two inputs and output or one input and two outputs like it depends how you want to like uh like name this operation for example uh why it's important because uh we cannot U sore 16 bit numbers why because we have our limitation of table size our lookup table should be like not more than uh our big execution table it's requires some field um field boundaries because like M multiplicative subgroup of the field

which we use for uh fft but uh like uh you can just assume that okay we have some boundaries and if we have like want to sore uh two 16bit numbers it will require us to go through all the pairs and it will be like 2 to the power 32 and we and our limitation is 2 to the power 20 maybe 21 uh whatever so we cannot but what what we can do we can add this by split table so if you have two 16bit numbers we can use this table to split it to bytes each number to bytes then we can use like sore table toore chunks separately and then we can concatenate

again yep and we have a range check it just checks that uh like usually it just use the First Column and the second two columns are just empty it just proves it Al so second two columns are just zero it proves that the First Column is like always like has 16 bits and also here we have like tables for shter 56 a b and c here would be a four bit elements and uh it will compute I think like this it's just for some sh 56 internal logic I'm not aware of sh 56 actually and like the algorithm itself

but yeah it use FL bit operations and we use this table for optimize uh sh of six computation uh primitive implementing the C I guess M and then just um okay I guess we I have covered what like our our minimum you know plan what I wanted to say but actually here is nothing very interesting it just uh tell how we usually Implement so instead of tracking okay what sell okay here we have already checked that it's buing and

then we put it what whatever we just use some abstractions from it's just you know like implementation details and for example we have structure bllen and we guarantee that the cell inside is always like blline checked or like check that it's a bite so have eight bits or has like 256 bits for example is represented by eight numbers of 32 bits and uh whatever and here's some just methods how you do it and uh yeah and we have like different other types that just it's just yeah implementation details like rescue like model arithmetic

elliptic curves uh I was just wondering whether a negative number can pass the range check or whether the range check function or whether it will fail negative uh number yeah uh so when when we deal with prime field we don't have like actually negative numbers so you mean like for example minus 5 right yeah but actually like for example we do something modu of 7 then minus 5 is just equal to two because uh because like it equals to 7us

5 is equals to 0 - 5 but 0 is actually equals to S because for example we do something modle 7 so equals to 7 - 5 so it equals to two so actually when we are talking about okay we have like couple of Beats that means that uh our number is like if you have some number like and says it's a bite that it's like from zero to 200 55 mhm okay any other questions when I have

like read it when I started to do the zero knowledge I really love it it's just interesting how for example you can uh make like some yeah conditional selection or how you can do some trees or other data structures so you can uh beat operations or whatever it's just interesting I recommend to read it if you got curious about Gates and uh and it's quite simple so maybe finish it just one hour and also I will find you uh BL article and an article about look up if you're curious about Mass behind pring system but there of course

will be like a lot of mass and more complex