Non-Native Field Arithmetic - Özgür Armanc Yiğit | Ethereum Foundation

hello everyone um yeah today uh I will try to explain non-native field arithmetic um it's a little bit low level slight but I hope I will I can keep you with me um yeah so basically why we are using non-native field arithmetic or why it's needed um okay basically this is usable when we deal with proof aggregation when we want to deal with proof systems we use scholar field and [Music] um yeah when we deal with group operations we use base field so we have two different fields and we we want to sorry our native field is smaller than our room field and that's why when we want to aggregate created proofs we need to use such a way to um we need to use such a way to create down our wrong field so we can use it as a network field um yeah that's the main idea here uh so yeah in here in the photo you can see that we have a field and fields are actually we Define a field then we sorry we Define a field and then we create a construct elliptic curve on from this field and um because we are why we are using ft curves because they provide us a group and we can do group operations uh after that yeah this is the main idea that we are first defining a field the first defined field is wrong field and we are defining our elliptic curve on from wrong field okay yeah you can see here that we have in purple we have field and after field we are defining our elliptic curve on from this field and we we have this group and we have several operations in groups Point Edition and point doubling um so Point addition and point of Link naturally gives us um scalar numbers after a point because if you want to take Point p and add another Point P you get 2p so that 2 is our scalar number and with this way we are getting our scalar field and after that we can do it we can use color multiplication on our field this is the basic order yeah um and here are the the first purple is our wrong field as I told and the native field that we create from group operations that naturally occurs that that's natural occurs and that field is smaller than our Run field yeah now we will use two different methods one is Chinese remainder theorem and other one is resident number system so we will use Chinese humanitarian to constrain equation to check validity this is pretty important I will show the low level part of this in the other hand RNs will be used for the calculations yeah we can start with RNs because I think it's a little bit easier so basically you can see that there is um if we use mod 5 we have zero one two three and four you can't get five six or seven because it will uh it will automatically like you will take the mode and it will be zero or one or two Etc but that doesn't mean that we don't have these numbers we can represent these numbers in a way and we can keep the data but still we can lower and we can use this in our calculations so um why this is important because we are inside Fields and Fields has a boundaries they are like a prime numbers and yeah we will keep this in mind and in the future that when we do operations like if we have 12 mod 5 we will know this is still 12 but we will represent this as is as a number two so Chinese remainder theorem um yeah this is a pretty nice theorem actually because um uh this theorem gives us a solution to a system of linear congruences in relatively prime models so um basically we can see in the example that we have X in five in seven the the represented number in five seven and modulus 11 right like two three four so we can use this three number and get a um get a number X that satisfies this equation in this case it's a little bit long example but in this case 367 mode 385 is our X that satisfies that three equation so this way we can use different numbers and keep data and build our original sorry check our constraint with this way and we can yeah we can know that we have different um like we will use wrong field and Native field two different modules and we can use this theorem to check constraint that wrong field number is satisfying inside native field okay yeah this is um a little bit uh starting it will be a little bit mathematical part and yeah we will Implement uh algorithm basically to show you how we do that um yeah we have several notations here um wrong field modulus we show it as a p and we have native field as n and we will have binary field 2 over T I will show this to you in the next slide yeah uh just to keep in this mind um I we can do multiplication addition Division and all of the operations but I will show addition because it is a little bit simpler and yeah easier I think um so here is a Formula that we need to follow this um it's actually very basic a plus b we are doing normal addition and Q times P plus r r is our remainder or result and p r p is our model and Q is quotation how much time that we wrap around our modulus so in this way this equation should be zero if it's not uh we can say that there is something wrong with this calculation okay um we need to calculate four different things to set to check this calculation um yeah we can start with intermediate sorry coefficient here oh sorry before that I need to explain at binary field what we will use this in Chinese remainder theorem um this is an actually so our native field is smaller than our wrong field as I told before several times so we need uh we need a helper field to leverage our native field so 2 over T is uh this should be very specific number uh to multiply with we need to multiply with our native field and it should be bigger than p square plus P because like P Square is coming from you can see that Q times P we have q times P if Q is the biggest number in P it will be P Square and if remainder is the biggest it will be P so p square plus P it should be bigger than that so we don't lose any data um we we already implement this in our project and uh in our project we use T as 272 we will this number can be divided to 68 bits of four limbs yeah um what is limbs so as I told we need to use some method to crack down our big number and use this binary field to keep data in each limp and with this way we can fill our numbers inside each limb and don't lose anything so you can see in the First theme we are keeping the first 68 bits in second we are keeping other 68 and other 68 so we will have 272 bits and it's already bigger than our wrong field because our wrong field is 254 actually native field is 254 as well but it's a little bit smaller so yeah with this way we are granting that we we have bigger field and bigger space for our numbers so yeah we can start with coefficient and the result and this is the actually the easiest one to calculate so in addition and subtraction quotation cannot be bigger than one there is a reason for that because if you take the the maximum number and add the maximum number you will just wrap around the modulus one time and you can't go more than one so that's why we are just keeping it in a short form and we are typing one or a zero but if you use this algorithm in multiplication or division you can get very big numbers so yeah this is just for addition and subtraction sorry for for the result part is actually after that we've wrapped around or not the result that we get basically is our results and quotations will be just one or zero so intermediate values yeah this is the part that it's um it will be a little bit lower level so yeah this is needed to check our Chinese remainder part actually so we we will calculate this um and after that we have a such a strange way like we have we are doing this for each limb and yeah we are using a negative um modulus inside notific sorry um we are using binary field inside negative wrong field and we are multiplying with coefficient so quotient sorry and yeah we are calculating this intermittent values it's little bit complex you don't um you know have to understand that deep down but basically with this way we are getting each Limbs and keeping data that we have a number that is bigger than our field if it's bigger that we can reconstruct or we can know that that number is exactly the the number that we write in the first part so if it's get wrapped around we will still know that we have these values and we can we can say that yeah we still keep keep the original that data and we can do constraints on them uh yeah after that we have residues and yeah in residues it's actually a little bit um different I can say um but let me explain left shifters and right shifters first we are using this a lot um basically left shifters is if you take the second one and multiply with um number sorry one lamp it will take that limp to the upper level so if you use these four left shifters if you multiply with your number that you cracked down inside limbs it will reconstruct your original number but it will be in Native field so if it's bigger than your native field you will lose data so that's why we need to keep these intermediate values on our packet so we we know that yeah it's wrapped or we can check constraints that it calculated correctly in the future in residues we are basically taking [Music] um sorry yeah we are basically taking each link from intermediate values and we are left shifting one time the second one so it's it gets to the up level and for um result part we are doing same and we are following this formula and yeah at the end we we get such a number with two limbs not four limb streams time results is uh are um down sorry reduced half size of the original limbs if you have eight it will be four but in the in our case we have four so it will be linked limbs are will be length of two and yeah we will follow this formula to to build our residues it's still yeah a little bit complex but we need to use this in the future calculation I will show you right now yeah so at the end we are coming to Native constraints uh and yeah native constraints are actually very efficient you can do this very easily so we we are just taking a plus b that I show you in the first place the formula we are just taking the right side to the left side and we are checking that if it's zero or not if it's zero we say okay this is calculated correctly but we are checking this in Native field so we say that in a native part this is cons this constraint is satisfied and we can go check the second part of the or constraint which is Chinese remainder theorem binary constraint this is um this is the actually important part for this um yeah we need to formula we need to follow this formula so we've built residues and intermediate values and residues from them and we are doing the opposite like we are doing reverting it and checking that if it will satisfy 0 or not so this is basically the the reverse calculation of residues and if these results returns zero than our constraint sets wise yeah yeah I would like to thanks my team Ariel Gibson and saiti mamolo who had to review this and yeah before I finish I actually forgot that I should mention this um yeah we we are doing these operations so um yeah I have a little bit time so we are doing these operations um because uh in rollup systems ZK roll ups if you ever heard about it so um you we are creating zero knowledge proofs um and we after a point zero knowledge yeah they are very cheap and they're very they are not taking too much uh size but uh there's a good thing they are always constant so if you want to merge the proofs you will get a constant value again right so with these formulas and uh sorry if you like follow this non-native field arithmetic to create it down and after you build proofs you merge them that proves and again and again and again you will just have one little constant size proof and it will have maybe like you can put inside like millions of proofs it will take a lot of time in prover site but in verifier side it will just take a second to verify that okay this roll up this all of these proofs are correct this is why we are using this this is actually pretty important for future of the ZK and yeah that's all um like I would like to uh if you guys have any questions uh I would like to answer and maybe show you maybe help you more about this topic it was a little bit extreme I think yeah so as I told um you guys if you you need to if you're not not don't know what ZK is I can explain a little bit more maybe to you so um ZK is zero knowledge actually is pretty uh nice way to verify that you know something and basically they are telling that that you know something but you are not leaking any information what you know but you can convince someone that yeah they will say okay this guy or I don't know they are telling the truth so we can use this in our ethereum Network so in the future it will be a constant size proofs and you will you will just verify them in a short time but the problem is um like um the creating proofs are actually a little bit expensive so like you can put I don't know 3D enough proofs like you can put every proof that you created inside your only one proof but it will take a lot of time from your approval part that's the actually that's the actual bad bad part of the ZK yeah that's all if you don't have any questions [Applause]