ZK12: Simulating Modular Arithmetic(s) - Dan Carmon

Transcript

[Music] thank you uh it's nice to be here so I want to talk about um a couple of experiences we had recently in stalker for implementing modular arithmetics over some Fields inside different fields uh and a little bit about the techniques and tricks that we use to do that so it will be a bit technical at some points right so first off is um we have a big field and we want to put an even bigger field inside that Big Field uh so more specifically we have a stone prover this prover proves chiro programs by compiling them into a stark as probably all of you know Stark proves validity of

an air in algebraic intermediate representation which is a list of polinomial constraint on the trace of a computation um and both um Cairo and this air that the star proves have a native regist of type which is a field element which we call felt over um a big Prime which is roughly 2 to 251 Cairo allows us to use basic operations called chyo steps and they include things like uh field arithmetic between elements on the stack so um one element can be the sum of different elements on the St or the product of different elements on the stacks we can have memory access so one element on the stack can be a pointer to another element on the St and we can do

reference V pointer and we have program flow depending on elements of the step whoever to go go to this instruction or a different instruction all of these things together are uh touring complete but you can do anything using these kind of steps but it can be very expensive to do certain things only using field arithmetic each one of these steps has a fixed cost in number of Trac Sals um and we want to minimize that cost to have shorter proofs to have um cheaper Pro time um so for that purposes some operations we allow us built-ins which uh Implement some of these operations directly by polinomial constraints instead of using the chyro steps which are very turned

into polinomial constraints so for example rain checking as was just mentioned can be such a builtin just direct polinomial constraints um bitwise operations you don't really want to do bitwise operations using field element operations but you can do it much cheaply just with uh polinomial constraints on certain elements similarly computer hashes can be very inefficient if done directly in Cairo but can be much more efficient in directly on the air and all of these things um are then given access to to the chiro programmer can use these built-ins with minimal interaction between chyo steps and and and the buildings so one example of a thing that we want to do is to allow field

operations in other fields um other than our native uh Cairo field for example for computing elliptic operations elliptic curve operations for cryptography on curves such as BN 254 or sep or bls2 381 um all of these are in fto Gaga library and the general idea for how to do this kind of arithmetic is to break down these big fi elements into limbs that will fil in a felt and actually we want products of such limbs to also fit in a felt so each of these limbs should have size which is at most half the size of a felt um and then we can use this lims to simulate modular arithmetics so we want to support here Fields up to 3

84 bits we know that's useful for that BLS curve so we decided to use uh four limbs of 96 bits each for this builtin and all of this decomposition again can be done in pure chairo but again it will be very inefficient to you have a lot of constraints here between these limbs to simulate this arithmetic much more efficient to do it as a buildin and this building is also very different from the other buildings that we have for example for range check how will the user use it they just provide an input to this range check built-in and then they know that this thing will be in that range uh for bitwise you provide inputs and you get outputs it's

very direct very low communication here we don't have something similar to that the interface is not that the user provides A and B and M and gets as output a plus b module M the reason not to do that is mostly that even this communication is very high so each of these a B and M as we said it's it's four field elements in itself so just writing these things down for the builtin and then reading the output from the building all of these already takes a lot of C steps in itself and it's not the common use use case you don't usually just want to do one operation module M you usually have a bunch of operations module with the same M usually have circuits for example if you want to do elliptic curve operations and each one of those involves a lot of

predefined steps of repeating the same kind of operations in that field it's much more efficient to build that um circuit provide the entire circuit to the built-in and then get the output of a circuit so the way the interface actually works is that the chiro programmer provides the modulus M which is fixed for the circuit a point a pointer to the list of all the values that will be the intermediate values um used in the Circ including prefill the inputs that they need and um two arrays of triplets each one gives us offsets to either an addition gate or multiplication gate so triplet ABC which says that either the value at a plus the

value at B is equal to the value C module M or the product is equal to that using this kind of cases you can also uh have get subtraction and division you just have to give a and C to be the values that are already known and then B is the deriv to be the division or subtraction depending whether it's multiplication or addition Gates and the the programmer provides all of these things to the builtin and the builtin then automatically fills in all of the values in the um all of the missing values in the values including the outputs that the programmer can then access or assert other things on and enforce everything with polinomial constraints and so getting a bit deeper into the

arithmetic how do we actually do the arithmetic inside these modu buils we want to verify that op a is C plus some multiple of the modulus M where op here is either addition or multiplication um for addition we only need to add K which is either Z or one assuming a B and C are all between zero and the modulus so either a plus b is between zero and modulus and then you K will be zero or it's um o over the modulus by by at most M so K will be one and for multiplication K can be as large as the full capacity of his lims um technically it can be at most M but we

don't know m in advance so M can be as large as 2 to 384 generally how do we verify that we compute we shift everything to one side and we compute that this thing is actually equal to zero by Computing it limb by Limb and uh observing the carries and writing constraints down on the carries so what it actually means to computed limb by limb is that for every limb we see that the I Lim of op B minus the I li of C minus the I Lim of k n plus the IUS one flim from the previous carry should be the next carry times our Ric which is 2 96 and this should hold for every I we

have four of these constraints for addition seven of these constraints for multiplication right 3 + 3 is 6 + 1 because you start from zero and we also need to constraint that these carries are in the proper range and this this range is plusus one or zero for addition because um everything here is just small limbs um and it can be up to slightly larger than 2 to the 96 for multiplication why is it slightly larger because um the I limb of of 8 * B or of K * m in that case is actually not just um up bounded by 2 to 192 it's actually a convolution of the product so for example the third limb of uh a * B

is actually A3 B 0 plus A2 B1 plus A1 B2 plus a0 B3 so it goes up to uh 2 to the 194 which is 2 * 96 + 2 uh so but Epsilon is equal to two um in fact all of this we can do we can save a little bit on these constraints by using polinomial evaluations and interaction so every element that we have here which is written as sum of Limbs times powers of a radics we can consider a polinomial that matches it with the same coefficients so from the polinomial you get the element back by just plugging in xal to 2 to 96 and we notice that this constraint

star on the carries that we had for each I is actually a constraint about coefficients of a certain polinomial that's written there which is op a x BX - CX - KX * MX plus this interesting thing x - 2 96 * carry and this multiplication by X exactly gives us the shift by one that we have from the carries that we get the carry from the previous one x * carry X the I coefficient of that is carry IUS one so the condition star is exactly equivalent to this polinomial Vanishing by Co ients on the other one we know that it's a very low degree polinomial it's degree 3 for addition degree six for

multiplication and our field is very large it's size 2 251 so to prove that this polinomial vanishes we can sample it at a arbitrary at a random verifier provided point and if that vanishes then almost surely this polinomial actually vanishes in all of its coefficients and we can save some constraints instead of having the four or seven constraint we said it's just one constraint but with interaction and actually for multiplication this also saves us a few multiplication operations because um we don't have to compute the entire convolution that we mentioned before we just have to evaluate A and B at points X and then one multiplication of field elements instead of

um instead of 16 and same for K evaluating is also eight multiplications but it's still a nice saving in in the number of multiplications that we have here so this is how to do multiplication for our bigger field inside big field with some some nice tricks and this trick also helps us for addition not only multiplication this polinomial evaluation trick so that was that was the first issue and uh the first item and the second one is simulating a Big Field inside a much smaller field our next use case is we are now working on St our next gener our next Generation Prov uh which will be for a

circle Stark over base field M31 we send the 31 mer number um and from from now on for the next two slides uh felt will mean field elements inside this smaller field um we use a smaller field because it gives us much faster proving time operations in this field are much much faster than operations in a Big Field in terms of CPU and so on uh but problem we have already have star exists it uses skyro it uses Stone existing programs already rely on the fact that the field is 2 to 251 we can't just abandon it and say that the field is actually 2 to 31 minus 1 and everything will work the same it

won't work the same so we have to support also the existing things that currently exist uh so we need St to also support operations over this specific finite field it's very important um we'll call the field of fat field F 252 to um distinguish them and what we know is VP is now fixed unlike in the modu builing that we discussed before which we wanted to support for um general moduli which we don't know in advance uh VP is fixed it's known and it's also very sparse in bits which is a part of the reason why it was chosen originally um we see that it only has um three powers of two here that appear at

all and with a small coefficient there and we will use take advantage of that property of P to make um the multiplication specifically more efficient so The Spar of P actually means that module of P some powers of two will also be various spse so how do we compute a large power of two modu of P we can see that the fact that P equals 2^ 251 + 17 200 2 to 92 + 1 means that module p 2 251 is -7 * 2 192 - 1 and if we multiply that identity by a power of

two but not too big power of two then we get that some powers of two up to P are just sums of -7 * power of two minus 1 * the power of two and similarly for negative Powers we get from the original definition of p that - 1 is equivalent to - 2 251 - 17 * 2 to 192 and if we divide this by a power of two then it would be just the same as if dividing one by this power of two will be the same as dividing the two other powers of two by powers of two and and they will remain positive numbers of two for small enough C so just as before we want to break

down our large field element into uh limbs that will fit inside the smaller field element we use 28 limbs of 9 bits each um and the reason for this particular numbers will be specified very soon and we want to make sure that the coefficients that we get here in terms of these limbs are small and for that we multiply by minus 4 so after multiplying by minus 4 and write everything down now in terms of this radics of 2 to the 9 so all of the exponents that you see in in these two lines are divisible by 9 189 is divisible by 9 is is the statement um we get that -4 * a power of two which is

above 252 is equivalent to exactly the same um formula that we had above multipli by minus 4 the 193 we took 16 out to get 189 which is divisible by 9 and we break down this 17 * 64 which is a number which is bigger than 512 are rics so instead of getting uh one limb with a very high coefficient we get it as two adjacent limbs the B+ 22 Limb and the B+ 21 limb with coefficients 2 and 64 and similarly in the negative Powers we have that 17 * 32 and that breaks down into the um 1 * 2 the 9 22 - c plus the 32 uh 21 minus

C and you can see here the reason that we had to have the minus 4 if we had for example -2 instead of -4 then that coefficient of 2 to the 9 22 - c would have been half instead of being one but half means that it actually goes back to the previous coefficient with a coefficient of more than 256 it would have been 272 together with that half of 32 and that's a much bigger coefficient than the maximum coefficient we have here of 64 similarly if we divided by two again then uh the coefficients of twos that we see here in in both lines would have become halves and and given us very large coefficients so we played around a bit with these options and we

found that um having a limbs of N9 bits with uh this coefficient gives us relatively low coefficients in in this kind of forms and we see that we want these things to actually be reduced modu P so we want them to fit inside our 28 limbs that we have and that is the case when B is between 0 and five for the higher powers and when C is between 1 and 21 so we see that the B+ 22 element um means that b cannot be bigger than five the 9B element means that b cannot be negative similarly 28- C says that c should be at least one and 21 minus C says that c should be at most 21

and the nice thing is that this gives us uh 27 20 seven more elements which is um exactly what we need so the full algorithm of how we apply this thing is we first compute a a * B minus C formally so each of these XI are actually from the convolution of a * b um and some of them have the minus CI Parts the sum goes here from 0 to 54 inclusive which is 2 * 27 um so some of these XI can be very large the middle one will be a sum of 20

I 28 products of Limbs of size 9 bits so it can be as large as 28 * 2 to the 18 after we computed that convolution we multiply it by - 4 * 2 to 1 189 and reduce module P so but this reduction is done by um taking that coefficient plugging it into the um the coefficient of the limb the 2 to the 9 I part and reducing that mod will P exactly by these formulas that we have so for I which is between 21 49 we just get that uh these are limbs inside the range of of 0 to 27 by themselves or 28

not inclusive and For Eyes which are less than 21 we get that these are negative Powers which fit into this formula with minus 9 C and for I which are greater than 49 we get that these are positive Powers but exactly in the range that fits into this 252 + 9B without overflowing and each one of these things in this range will give us will match with three of these yjs that we have um so each YJ will be the sum of a few of the XI with some coefficients that we got from those formulas some of these X I will contribute to three yjs some of

them will contribute to a single YJ um on average it's about four X's per y after we get all of these y's again they're not reduced they're just formal sums with with its coefficients uh we want to finally show that V sum is z modu of P that's the whole thing that a * B- C is 0 modu of p uh so we need to find the coefficient K of P that will give us this formula and actually this coefficient will be very small it's about as small as the y27 coefficients divided by 2 to the 10 Which is less than 2 to the 18 which is which is very nice Definitely fits inside a felt inside an M31

element and after we have V K we just prove everything by constraints on the carries exactly as we had um in the mod builtin without here the trick of uh polinomial evaluations because actually here the degree is not that small and the field size is not that large so the soundness of evaluating on a point here inside the field will not be as good as it was for the bigger field um and and the cost of of writing down these constraints is also not that high on the other end and as you said the parameters for 28 and 9 were chosen exactly uh so that all of these things together with the coefficients with the reductions we don't get any overflows of the 2 to the

31 field so it actually all fits together doesn't even overflow 2 to the 28 if I'm not mistaken and uh that's it [Music] [Applause]