Non-Native Arithmetic via CRT Codes by Liam Eagen | Devcon SEA

[Music] coming to my talk um in writing the talk I found that I think it probably makes sense to mostly go over sort of what non-native arithmetic is and sort of build up to the question because this is sort of an idea I've been casually thinking about for a while and I don't have like um you know definitive answer to yet so yeah um do I push the button or how does that is this [Music] working the the clicker oh wait it is working okay okay so um for people who don't know uh what what is like uh the context for all of this so um non-native arithmetic is something that comes up in snarks which are succinct non-interactive arguments of knowledge may have heard of like zero knowledge proofs um and this is the same kind of thing um so in a snark uh some party the prover wants to convince the verifier that they know some witness um um and they want to do this by generating a proof without interacting with the verifier so non- interactively and the proof should be small and uh if it's zero knowledge it keeps the witness secret um yeah and sorry for the formatting I did the slides in Beamer and had to import them to Google Slides so might be a little weird but um yeah so the way that we usually write this is there's some C which is like a circuit um that has some public input X and some private input W and the protocol allows the prover to convince the verifier that they know W by sending a proof um so for example right you could have some like chain State X which is public some transaction W that is private and you want to prove that you know W for a given chain State and so not all transactions will be valid um and so that's what C checks um yeah so the the cor of important takeaway for this from this for our for our topic today is uh that c is defined typically over a field so a field is like a place where we can do arithmetic addition multiplication Etc and uh that field will be defined modulo some prime P um the field is sometimes sort of like a free parameter depending on the proof system you can pick the field freely uh and sometimes it's not so if you're using like a stark you can sort of in principle use any Fields just some caveats but for like an elliptic curve based proof system it's usually fixed as part of the the curve which again depending on the particulars is something you probably can't control um so the question that motivates non-native arithmetic is what happens if we want to prove a statement about some arithmetic that lies in a different field than the one that we're defining our relation over so right suppose you want to verify a signature that is defined over some other curve externally to your proof system right you want to verify um a Bitcoin transaction or something inside of b254 and uh in that case both of your Fields will be fixed and you can't you know change them and they're different so you have to simulate one field inside of the other and uh yes so we need to emulate or simulate the non-native field inside of the field that our relation is defined over um so just like as a simple example of of why this doesn't work right uh suppose we wanted to check that like 4 * 5 mod 7even you know you can check that that I think all the arithmetic there is right and uh 4 * 5 is 6 mod 7 but then if if our proof system is defined mod 5 then you know directly carrying out the computation will yield the wrong result so they're fundamentally different spaces for doing arithmetic and so you need to simulate the one inside of the other um so what can we do uh the situation is not hopeless uh like in principle right this is this is a solvable problem because you can simulate or you can encode any NP relation into an arithmetic circuit over any field um you know you can encode it into binary digits and check that the digits are binary and encode the bitwise operations and so this is just sort of like an existence proof but this is you know very slow and we would prefer to do things more efficiently than this and intuitively you'd kind of expect it to be possible to do so something better because fields are similar right they wrap around but for small values they behave kind of like the integers you're just adding numbers and if you don't exceed the modulus then maybe we can exploit that somehow that's what we're going to try and do um so the first observation is to check modular arithmetic we just have to check integer arithmetic because if you want to check something mod R this is the same thing as just checking some integer relation for a quotient uh and in some cases this is actually sort of Enough by itself so depending on the relative sizes of the fields the it might be possible to do this like if you check that a b c and Q are all small you can just check this relation as written here directly in the larger field and the reason this works is because it will never wrap around the larger field um so if all the sizes of everything are small or provably small then uh if it's equal to zero mod P it has to be it has to hold mod R um you can convince yourself of this I think it's not uh that strange right because if something has magnitude less than p and it holds mod P that means it's zero mod P and since it has magnitude less than P the only thing that's zero mod P with magnitude less than p is zero um and so this this works sort of like up to square root of the size of the field basically um and that that's coming from the fact that we're checking a multiplication if you were checking a degree 3 thing then you'd want like cube root or something like that um but what if our you know Fields not small or our modulus is not small right maybe it's even bigger than the prime that we're working over um then then you can't like expect your encodings of the small values in the larger fields to behave well and in fact it might not be possible at all if your you know elements are larger than the field that you're carrying out your or you're encoding your relation into you can't even commit to a big value in a single field element so this technique I think originally or at least I I first heard about it from um Aztec but uh there's this you know ancient um theorem the Chinese remainder theorem that allows us to work around this problem um and so what that says is if you want to work in a big modulus it's sufficient to work in two smaller moduli that divide the large L one or that multiply to give the larger one if they're co-prime um and uh it's it's sort of like you both sides of that are are rings right so you can take a value and instead of working mod AB you work mod a and you work mod b and uh these two rings are isomorphic and so people call it a residue number system and you can represent a large number number mod AB by representing it by by encoding all of its residues mod different small primes that divide AB um and I here I've written it with two but you can sort of recursively apply this this uh equivalence to include arbitrary numbers of co-prime divisors um and so remember we were working mod P and we had some R and our R might be too big but now we can pick whatever modulus we want right we can pick a bunch of small primes so it's always large enough to recover the uh value that we're operating over um and so long as everything kind of remains small that Q is supposed to be a product but uh so long as everything remains small um this works and uh like before how we didn't want to wrap around P here we would don't want to wrap around M but here m is a free parameter it's not fixed by the proof system okay so now like a slight digression to explain the idea um read Solomon codes are an error correcting code scheme that is ubiquitous in in snarks uh if you've heard of starks or fry this is you know essential to how they work um and the basic idea is we have some message that we treat as a vector of Dimension K and we encoded as a polinomial as the coefficients of a polinomial uh and then that polinomial we evaluate at more points so remember a polinomial of degree K or k minus one is determined by K points and by evaluating it at more points you're adding redundant information and so like in the original conception of read Solomon codes this was to deal with the fact that some of the information might be corrupted um so you only need like even if some of the data is is uh maliciously altered you can still recover the original message um certainly given all of the points you can recover uh so given a polinomial and we evalua it at some set of end points this is equivalent uh to reducing the polinomial mod this kind of uh uni like um degree one ideal x minus RI um and so this Insight allows us to generalize read Solomon codes to other like you know domains um ideal domains and for example algebraic geometry codes which replace place um polinomial and uh evaluations with functions of some curve and divisors uh can be cast in this language as well and um this is also how we're going to introduce uh CRT codes here CRT is still Chinese remainder theorem so the idea of a CRT code is rather than encoding our message as a polinomial we encode it as an integer and then rather than evaluating the polinomial at multiple points we take the integer mod a bunch of small primes and so you can think of these mod small primes as analogous to evaluating a polinomial at a point um it's not exactly the same right because the the ring you get from reducing mod different primes is not the same but the ring you get from evaluating at a point is always the same that it's not really important for our purposes um yeah so if you have enough primes so that the product of all the Primes exceeds like the bound of your your original sort of space of integers that you're encoding into then even if some of the primes are wrong in the same way that with the read Solomon code you can correct errors with a CRT code you can also correct errors um and this encoding is the same as a residue number system so you're taking an integer you're reducing it mod a bunch of small primes you're keeping the residues and you can just work with those um and for for those who are familiar there's a lot of similarities here with with how um you know Starks work and uh other kinds of algebraic proof type stuff okay so this slide I just screenshotted because it was horribly mangled by the formatting so the sketch of the protocol is suppose we want to verify some non-native arithmetics we have some system of polinomial equations the F in in different X's which are integers and uh the fs have degree D and all the integers are bounded so in the original version of this right we'd be checking um arithmetic mod some other Prime and you can encode that as an integer relation and so the primes are fixed in advance and you have some M which is larger than the kind of Maximum value achievable by F uh as written it's it's a little wrong because you probably want to account for the additions but you know something like that and then you encode your integers mod all the small primes as we described and uh also provide quotients for the evaluations of these functions I guess that's written that those should all be zero so maybe there's a slight confusion there but yeah so you prove your encoding of all of the integers is um sort of within its appropriate range and then you choose a random subset of the primes to test the relations over and uh for Simplicity assuming the primes are all like roughly the same size then you can calculate the success probability of a dishonest Prov pretty straightforwardly um you know it's just the probability of having like some code word right some set of residues that does not correspond to a small integer uh or that's that's like wrong in some position and then uh yeah anyway um yeah so it's similar to how Starks work um okay yeah okay so this is the interesting stuff um as described in the the previous protocol um we're testing each encoding of X is close to a small integer directly you're just taking your set of residues and like checking that it is close to a small integer or um an integer within the right bound um this used to be how like fry based proofs did things but it turns out that there's a much more efficient batched proximity test so proximity test here is you're testing the closeness of the set of residues to its space of correct messages and what people do now with Starks is is uh take a random linear combination of encoded columns or encoded integers and test that the random linear combination is close to code word um so instead of testing each one independently you can just take a random linear combination and test that one thing so the question is can we do the same thing here with CRT codes so uh I think so uh but it's very it's very different right because in the read Solomon setting you have polinomial and you're working over a field and you're taking a random linear combination over the field here we have a set of integers and we're taking a random linear combination of these integers but there's no obvious base field in the same way that there would be for polinomial to take a random linear combination over so instead we would pick a random integer linear combination to take of the the integers and this has a lot of interesting issues so for example ex Le this is not sensitive to encodings of small rational numbers if you encoded like2 then there's like a one and two chance that a random linear combination will cause the one/ half to go away uh and you might think well we could pick primes to multiply by but that doesn't really work um so it is in some sense fundamentally different but I think that it's it's possible to do this the question is just like how good is it and if if those things can be worked around so for example for working mod R this is kind of fine CU small rationals are also valid sort of to reduce mod R for large R but there's lots of details to be worked out so yeah just just some overview of the things I haven't talked about in this uh this talk so I mentioned a little bit that CRT codes the notion of distance is a little bit subtle especially if the primes are not all like the same size they can't uh sometimes always be I mean right like every Prime is of a different size so um you have to account for that it's not like a fundamental problem it's just a little more complicated um as well I mentioned this decoding to uh rationals rather than integers which in some applications is fine it might not always be fine so have to work that out as well well and then um another thing I haven't talked about but that could actually be you know worth considering in practice is all of this generalizes from integers to number fields and in number Fields you have a sort of different situation where the first point you actually can have primes that are like of the same size right if you have some prime over the rationals or the integers that splits over a number field then that might yield like a more convenient thing to work over and in some cases this this sort of works um and then you have to ask like how do you define the size of things and and so on but just more technicalities I think and then one other interesting uh thing worth considering is so we we move to the integers and we were no longer able to take random linear combinations over an extension of the base field but what happens if we work over Starks with polinomial and instead of taking a random linear combination over the base field we took a random linear combination of columns by random pols not over an extension field in in this way it's sort of analogous to taking an integer linear combination of integers and it has a lot of the same problems but uh it would allow us to avoid ever working with extension Fields potentially so I think that would be an interesting direction to explore if this work ends up making sense um and that is all I have thank you all right thank you so much Liam uh we do have a question here could you repeat how you calculate which primes are small enough to use for creating a CRT encoding um so I guess there's two ways to or I'm not sure what the question is referring to but for encoding into like a residue number system the primes can be any primes um that you you usually choose them to be small because working mod small primes is much more efficient um it this question could also be talking about the the example that I gave where you can simulate arithmetic mod a square root sized number in a larger field and that is just coming from the fact that the the relation that you're calculating over can't exceed the field you're operating in so you're you fix some field that you're actually working over and then if your field that you're simulating is small enough then uh everything kind of just works out as long as everything remains smaller than the characteristic of the larger field all right perfect uh we do have a little bit time for questions so let's give it another 10 seconds to see if we have any question uh what is the size of the coefficients in the RLC such as that security is still 128 it's a great question I'm I'm not sure I think uh I mean you can sort of work out that it they need to at least be drawn from a space of size 2 to the 128 but I don't know how much l you get from the uh protocol itself so I would say at least two to the 128 um sized space all right perfect thank you so much for the amazing talk William uh so we will resume at 5 for our next talk