ZK9: Bridging blockchains Foreign field arithmetics – Anaïs Querol and Joseph Spadavecchia

Transcript

foreign [Music] so for this talk we're actually going to be talking about foreign field arithmetic and I guess bridging blockchains on the two speakers are Anais and Joseph from o1 Labs good luck and welcome yeah yeah hello yeah I guess it's fine um yes so welcome everyone Thanks for attending this talk my name is Anais querol and he's my colleague and co-worker Joseph sparavecchia we're both cryptography engineers at all one labs

and today we wanted to present an ongoing project and we entitled this talk breathing blockchains foreign Phil arithmetics so I lead to Joseph to explain high level uh what this is about hi um so yeah foreign field arithmetics that seems like quite a low level thing it's also an interesting problem in cryptography but to understand it we want to kick things up to the high level really high and we also want to do a metaphor since we're in Lisbon and we have these beautiful buildings tiled buildings they're very unique here we thought it'd be cool to do it that way so we'll we'll

talk about blockchains as buildings in Lisbon um so yeah so the analogy is that um the bricks of the building or the blocks and instead of verifying blocks we're verifying the structural Integrity of the building by verifying each individual brick and checking its structural integrity and getting the the Integrity of the whole building that way um so the problem is if it's there isn't you know if there is a problem then this is expensive to to detect so right now most blockchains to get full blockchain security peers

need to connect to the blockchain and download all the blocks since last time they connected they need to verify those blocks and if it's a smart contract platform then they need to Recon rerun computations that are happening so all of this is very expensive and we wonder is there a better way yeah so now I'd like to ask in the audience feel free to just uh speak up if you're if you're brave enough so as a user in order to verify the blockchain it's a bit tedious to just go blog by blog uh checking them all so we're at CK Summit do you think do you know any idea that we could do in order to make this

computation a bit easier yes a snapshot yeah every a certain video blogs and then this snapshot the root of this snapshot is packaged into the consensus protocol so that makes things happen but uh uh I mean that's several years ago so it should be better now okay um well that was a solution maybe a complex Solution that's not the solution that I was looking for but thanks a lot for for participating I guess there's someone else there

uh yeah you you went uh to the very next slide so yeah thanks uh you're a bit ahead so uh yeah actually the concept that I they're very uh basic uh concept that I wanted to introduce is snarks right we are adding snarks on top of complex computations to make the actual verification uh simpler right so we're in Lisbon I'm sure you've seen these tiles in on top of buildings voila so yeah uh what happens if we put a tile like a ceramic tile on top of that shade of the building to check the Integrity of the blockchain so if there's any problem with that building the ceramic tile will basically break so you as a

verifier you it will be very easy to realize if there's something wrong because you will just spot it very quickly if the tile is broken so this is what snarks are could be used for uh so this is very good for verifier but it's not so good for approver because now every time you add a new block like a new break to the to the building you have to remove that tile entirely and build another one for the increasing computation so that's not very good for the proverb so can we do anything better uh any idea and I guess uh you I don't know your name but he suggested something which is called recursive snarks so that's precisely the solution

that I wanted to talk about so in recursive snarks we are trying to split that computation into incrementally incremental steps so instead of having like a huge ceramic tile covering the whole fashade we're adding smaller tiles like in Lisbon so now in recursive snarks you have one smaller proof uh there the blue one and that tile attests for the validity not only of the of the current break that you're adding to the blockchain but it also is connected to the previous proof like it's connected to the previous tile so inductively this means that one single tile one single recursive snark a

test for the validity of the whole blockchain up until the Genesis block okay so this is what recursive snarks could be used for and this is not something that we just imagined today this is actually being used in practice so this was all to introduce the Mina blockchain this was the first succinct blockchain that allows verifiers to and end freeways basically to have a proof of the whole blockchain by having one's iterative step so you just have to download one single proof at that single proof will give you the security that the current block is fine but also the

previous proof was fine until the very end so yeah this is what Mina is about and the actual tool that performs this computation is pickles so this is a protocol that takes care of the recursion step and it uses the pasta curves Palace and investor in order to provide support for the Halo 2 incrementally verifiable computation Style but the actual snark that runs inside is a a plunk like proof system with 15 wire with uh witness that we call kimchi it has support for lookup and runtime tables to support more efficient

computations and a number of custom gates to extend the functionality of of the type of circuits that we can prove things about and just to give a bunch of more details the polynomial commitment scheme inside kimchi is based on the bulletproofs in a product argument and and this is to support a fully trustless setup and now my colleague will explain how as a user we can profit from these benefits okay so cool so we have this great platform a succinct blockchain a great proof system that's got a trustless setup and but we want to do more than just verify

transfers between users on a blockchain we'd like to do a smart contract functionality and and so for that we've developed a tool called snarkyjs which lets users specify essentially Azure knowledge smart contract and then that can be compiled down into a ZK app which lives on the blockchain and this has two really good features that come along with it first is privacy so when users interact with Azure knowledge ZK app then they're able to hold some information whatever they like private and just generate a zero knowledge proof

that interacts with the ZK app and allows it to update the state on the blockchain the first good thing privacy the next cool thing is that um we're able to save a lot of computation so in a normal smart contract blockchain every time you interact with a smart contract those those instructions need to be replayed by all the nodes in the network but Mina we just need to do it once that could be by the user if it's a privacy Centric kind of interaction or it could be done by snark workers in the network but the point is the computation happens once to generate the proof and then from then on the nodes just need to verify that that's snark proof

um so that's pretty cool um even better because we're doing recursive snarks we don't have to verify individual proofs they're all compressed into the one blockchain proof so this is very very efficient um so this is great we have this cool platform um but we're still not done and how does this relate to foreign field arithmetic um well that's going to begin now so we don't want Mina to live in isolation on its own and just be this internal thing we wanted to actually be able to reach out to other blockchains and even real world things and interact um

and so this brings us to the idea of bridging and bridging is pretty cool and you can look at it in a lot of different ways and in our case we're we're focusing on a bridge between Mina and ethereum and if we look at the ethereum side of the bridge we have some really cool new things that are possible because Mina is a succinct blockchain we're able to do really neat things like upload a proof of the Mina blockchain State into an ethereum smart contract so actually within ethereum kind of lives I mean a full node and this is only possible because Mina is succinct then smart contracts and ethereum can

interoperate with Mina in a trustless and decentralized way no trusted third parties no you know Committees of nodes to trust um so that's the ethereum side kind of injecting Amina into ethereum on the other side within Mina well unfortunately we can't trustlessly verify ethereum and Mina because ethereum isn't assessing blockchain so you know I mean it would have to download all of ethereum which is not going to happen but there are still lots of really cool and useful things we can do and one of the things we'd like to do is verify things in ethereum and one thing

is signatures so what we'd like to be able to do is to create a proof of the verification of an ethereum signature in you know um so this is the the the goal in the subject of this talk yeah but that's not easily done right no there's a problem yeah so yeah so the problem is that um ethereum and Mina they use different cryptographic Primitives in particular they have different algebra and and so we need a way to solve this problem yeah so they're pretty compatible in nature uh so you can see that cloud it's raining that's a problem

but we can solve it so yeah let's take a look at that cloud uh this incompatibility comes with the shape of a Nissan DSA algorithm uh yeah elliptic curve digital signature algorithm um so basically we want to verify SEC p256 K1 in cdsa but over pasta curves so that sounds already a bit tricky right so in order to do this we basically need support for group Edition and group doubling where the group is different to that of your own language that of that of your own proof system um we will also need support for kitak like shot 3. this is a very snarky friendly hash function yeah this is a

pain so we basically have to encode all sorts of bitwise operations such as store and bitwise rotation this is a pain very simple very fast to compute but very difficult to verify but this is not the tone the the focus of of the talk instead we want to take a look at the actual foreign field arithmetics so in order to address group addition and group doubling we realize that we need support for two Primitives two functionalities with our foreign field addition and foreign field multiplication and in particular today we wanted to explain a bit high level would this form field multiplication is really about

so yeah um I'm trying to make things simple and actually they're pretty simple uh so I really hope you can follow and if at some point you have any questions please feel free to ask okay so this is the Youngsville problem that we are facing at this at this point uh so we have two numbers A and B there are 256 bit length and we want to multiply them that's it okay so we want to generate a C and C could potentially have 512 bits okay things are getting pretty long already and this is integer multiplication but in cryptography we barely ever work over integers and actually we work over

modular arithmetics um yep but not only that but in foreign field arithmetics we work over a foreign modulus so we work over a field whose module is f and basically this F could be larger or smaller than our native field so in particular for a use case in Mina and ethereum it happens to be the case that 256 bits for the ucdsa is one bit larger than the 255 bits of pasta so yeah there's an issue here and it's pretty obvious uh I'm I guess anyone could say it so we have a space problem we have many things that do not fit in

our buckets so yeah we basically have to find a mathematical way to to solve this uh space issue and we basically have two tricks that Joseph will introduce and that will help us sort this out go for it yeah so um so yeah as Anna said we have two tricks um um this approach is approach that was developed by Aztec and what we've adapted it to kimchi and the first trick we use is the Chinese remainder theorem and that says that if you have two coprime values and if the equation above holds for

both of those terms then the equation holds for the their product module of their product um the next trick we have is we need to do arrange checks we need to check that each side of the equation is less than the product of the moduli N times n um so in order to do that we do the range tracks and if that's satisfied then this equation holds over the positive integers so putting that together yeah so putting it all together yeah you have um we have um the situation where we we've done the

range checks we only need to check the equation holds module n which is our native modulus so that's cheap don't need to worry about that and modulo M so we need to find an m such that we can when we take the product with our native modulus we can fit all the Foreign Fields that we'd like to support and also it's cheap enough in our case and also cheap enough because if we choose you know 512 bits we end up with well it's a detail that isn't presented here you end up with a lot more constraints and it's harder and more expensive to constrain so we need to choose something that's efficient in kimchi our proof system so it turns out that

264 bits works very well for us it covers the use cases we want and but that's wait a minute here this is still bigger than our native modulus which is 255 bits um so what's going on here well that's okay because it's less than the 512 bits if we did it in some naive way what we do is we take the 264 bits and we split it up into three Limbs and again this three is something that turns out to be optimal in kimchi so now we've split up our foreign field elements into these 264-bit values which are comprised out of 388-bit Limbs an important thing here is that when we build out our constraints we need each

limb to fit in the native modulus but we also need it turns out the product of two limbs to fit in a native modulus and in this case this is satisfied because we have 2 times 88 which is 176 bits which also gives us plenty of space in the native modulus to do our constraining yeah so we basically have to decompose numbers and then treat the equation accordingly so this is the question that we really are carrying about all the time so we basically want to split those numbers into limbs so here we have the high limb the middle limb and the low limb and here I'm referring to the least significant bits on the right and the

most significant bits and left um so yeah we we basically decompose them uh take take the take the common factor giving us uh the limbs position uh we get that out so so we have like a nice picture of what's going on basically so yeah this starts feeling a bit complex there's a lot going on there's a lot of multiplications there will be lots of numbers going back and forth so yeah there's plenty of room for for for mistakes so we have to figure out what's the right way to treat this correct so we preserve soundness and incompleteness so one first step to do

that is let's take a look first at the very top part so let's take a look at what's before the equal term so a times B plus the quotient times the the frame field so let's take a look at that and let's just compute that so if we do that we will have limbs being multiplied with each other and duplicating the the length of of the of those products so we call these terms intermediate products this is like an auxiliary value that will help us uh constrain this equation uh correctly uh you might wonder why we only have three because there seems to be many more operations here going on but the good

thing is that since we are doing modulo we are doing operations modulo M which is 2 to the 3L anything that is larger than that is congruent modulo M so we can basically skip that and that's a reason that this type of constraints will be somehow efficient that's why we chose such an m so yeah we basically have these guys and in order to do the computation easier we'll just place them nicely like we will lay them out in a bit wise fashion so yeah this is the type of operation that we are now interested in we basically send the result to the other side of the equal

and basically if we're facing a real witness then that operation should be zero right because this is just the definition of the multiplication so yeah this is what we're looking for and we just have to constrain that so I think we can already see another problem uh which is the same problem over and over again which is I know you all know which is size right um if we cannot have 2 to the power of 3L elements we for sure cannot hold two to the power of four L elements so yeah you know we have to do something uh clever about this so what can we do because we can only represent up to here

right we can only Fade up to here so what can we do we can just split yeah we split so we will split this equation into halves bottom half and the top half so since the whole equation should be zero also the halves should be zero so first we can constrain the the the bottom part so we constrain that these equals zero and then if there's any carry with which might be we propagate it to the tube half and then also the top half will be zero so yeah by doing this and considering that this is zero and I'm missing yeah I'm purposely missing some details here to make this simpler but the idea is that if this is zero then you know that

the foreign field multiplication equation also holds so that was it form for multiplication but this is not the only gate that we need in order to support ecbsa and he will be giving you some details about the rest of the case that we had to include right cool okay so we have a form field multiplication custom gate in kimchi but to do the elliptic curve operations required for ecdsa we need a lot of other custom Gates so this diagram gives you kind of a pictorial representation of some of the metrics of these new custom Gates so foreign field multiplication and this is taking up two rows and it's using one 12-bit lookup

that's represented as the dark blue flowered tile then we have a range check sorry a form-filled Edition custom gate which doesn't use any lookups and it's only a single row and then to do the range checks we kept referring to a multi-range check and the multi-range check is what you see at the bottom of this figure it's three range checks and each of those is range tracking 88 bit values and this requires four rows to do it in kimchi um yeah so this gives us the gates but on top of the gates we have more work to do and that is to build out the elliptic

curve algorithms so group addition and group doubling that you heard about at the beginning of the talk um so to give you an idea of the kind of costs of these things group Edition is taking three multiplications 12 editions and 12 multi-range texts for a total of 72 rows per addition doubling is taking four multiplications 14 additions and 16 multi-range checks for a total of 94 rows for yeah so as you can see most of the complexity comes from the multi-rain text and that takes uh most of the rows so we're thinking about ways to optimize this so if you have ideas we will be open to discuss

because we want to reduce this number of rows this is just an unoptimized version but we're working on it so yeah feel free to reach out to us yeah so there we have another version It's experimental that requires fewer multi-range checks there's also been some interesting work published casting out primes that we've been looking into so this is a work in progress what we already have implemented all the gates and we're working on the gadgets and then eventually building out ecdsa and ketchup um so yeah thank you for listening and we're really happy to answer questions [Applause]

[Music] [Applause]