ZK Circuits for Elliptic Curve Operations in Halo2

foreign [Music] welcome everyone and thanks to Barry and yingtong for the great introductions so today I'm excited to tell you about this elliptic curve Library we've been building in Halo 2. okay so first let me tell you what the library can do so it's a Halo 2 library for doing various elliptic curve operations that in particular has a configurable trade-off between the proving time and verifier cost so the operations we can support is that for generic elliptic curve you have to put in a few constants we can do addition doubling multi-scaler multiplication and then for pairing friendly curves we can do optimal eight pairing verification and we can also do ecdsa signature check so we've also put this Library into the scroll and PSC aggregation circuits for the kzg back end of Halo 2. okay so before I tell you more let me show you some numbers so for ecd ACS for ecdsa signature verification you can see that if we have a small proof size at the top we have a longer time around 10 seconds a little over and then if we increase the proof size we're able to get things down to around three seconds on a MacBook Air weirdly we found that on the CPU the MacBook Air beats a fancy AWS box uh for a multi-scaler multiplication with 100 base points we can get things to around 56 seconds using larger group size and as you can see that's still an improvement over the small proof size setting and finally for pairing check on bn254 which is the curve on ethereum we can do that in about 15 seconds again on the MacBook Air okay so let me tell you how we build all of these circuits so we have a very modular approach so in Halo 2 you're allowed to use a lot of custom Gates but we're very simple minded so we use a single custom gate our gate is has four vertical cells and unfortunately I forgot to highlight them but starting from the top our gate is just a plus b times C equals d so in this example on the right if we want to compute a DOT product of one comma 3 with 2 comma four we're first going to apply a gate on the top four cells so that will say 0 plus 1 times 2 equals two and then we're going to overlap it with a gate on the bottom four cells so that would say that 2 plus 3 times 4 equals fourteen so this simple overlap optimization gains us about a 25 gain for all dot product operations which turn out to make up maybe eighty percent of all of the operations we do um so our setup is that we have a number of advice columns with this custom get enabled we have a single lookup table for range checks and then we have a bunch of selector columns okay so we set wrote a pseudo layout or in halotube which allows us to configure where these columns are placed in different regions so as a configuration to our circuit we allow a fixed number of advice and fixed columns and we sort of Tetris these vertical concatenations of our basic gate into the columns on top of this we built a basic Library called Halo 2 base of basic gadgets like inner product range check indexing into an array doing various bitwise operations and doing comparisons on top of the skates and that allows us to almost completely abstract away the manual signing of cells that you may be familiar with if you've written some Halo 2. so on top of that we build our elliptic curve Library mostly maybe 95 only using these abstractions one thing to note is we found it's actually very difficult to outperform using this very simple gate using fancier custom Gates we tried a number of what we thought were very clever things that did not improve the proving speed finally I wanted to mention one very critical optimization that we made which is that we previously enabled lookup arguments on every single column and that was crucial in doing our range checks we did one optimization to have special columns whose only purpose is to hold cells that are looked up and we copy all cells we want to look up to those columns although this sounds a bit trivial it actually reduces the proving speed by about the approving Time by about 50 percent and again we can configure how many of these special lookup columns we need depending on the circuit okay so just to show some plots on the results if we're if we vary the number of columns um the as the number of columns grows the proof size grows and typically speaking the proving speed will increase so you can see for the optimal eight pairing for a single column setting the proving speed is about 250 seconds on the left and as we expand the number of columns to around 15 we get pretty sharp drops in the proving time but things sort of plateau after that on the right TC a very similar phenomenon for ecdsa verification um we were a little bit surprised that things Trail off at this small number of columns and we're sort of exploring whether there's something in the back end which could have let it let us push it further all right finally I want to tell you how we plug this in to the existing aggregation circuits so if you have a kzg backend Halo 2 proof then to recursively verify the proof you need to do two things first you need to do a bunch of multi-scalar multiplication on the kcg commitments that comprise the proof so these would be multi-scalar multiplications on the BN 254 curve and secondly you need to do a pairing check so in the current aggregation setup the pairing check is deferred meaning that in the aggregation circuits only the multi-scalar multiplication is done so our Target was to integrate our library into the existing aggregation circuits so to our knowledge there are two one is out of PSC it's this Planck verifier repo and one is out of scroll which is Halo 2 snark aggregator the way that both of these work is that there are various generic traits for an elliptic curve library that they use and they sort of abstractly write on top of these elliptic curve traits so very nicely that that allows us to plug our library into these aggregators simply by you know re-implementing all of these traits in our language and again a nice feature is that both of these libraries are able to Output evm verification code for the final aggregated circuit so here's the results so in a setting where we have seven advice columns and eight fixed columns so of the advice columns six are standard columns with this basic gate enabled and one is a lookup column we're able to verify at the actual zkvm circuits recursively so we just tried out the evm opcode circuit and then the combination of the evm and state opcode circuit and so even on a MacBook Air we're able to do the recursive aggregation of the evm circuit in a little bit over you know around 10 minutes note that the scroll and PSC numbers are not precisely comparable because we have slightly different versions of the state circuit inside unfortunately when we aggregate the evm and state circuit together it exceeds the memory con constraints of our MacBook Air but we'll try it on the server soon enough okay so that's it so in summary we have this Library Halo to ECC we can support pretty much all the operations that we know of that you'd want to do on elliptic curves so some highlights would be the pairing check the ecdsa signature verification and the ability to configure the base curve without too much work and we really wanted to highlight that our base component Library Halo 2 base which we open source this week which allows us to write these circuits in a much more modular and configurable way thanks and I'm happy to take any questions [Applause] are there any questions okay I I have a question so I I am one of the authors of the Halo 2 Library so if if you could change two things about Halo 2 what would they be no more if you ask me for two things the first thing would probably be and this might be very difficult to change so Halo 2 has a function called synthesize which constructs your circuit but the design of the library is that synthesize is called multiple times with different purposes and different interpretations of the input so when we're developing that's actually the biggest source of bugs because we sort of forget that on one of the times the mean semantic meaning of some of the inputs is a little bit different I don't know how that would be pulled out but that's the biggest difficulty right now okay um and also oh is there a question no um Halo 2 is a very low level um API in the sense that you can configure really every detail about your circuit so have you found that to be more helpful or more annoying we really like the configurability and that's why we're spending so much time in the Halo 2 ecosystem uh the way we found initially we found it very difficult to manage but the way we found to be productive in it is to sort of really restrict ourselves as you've seen here and then slowly add on more complexity almost as not really a pre-compile's not the right word but just almost as a special addition to our library and then restrict ourselves to only work within this sort of constrained universe of the freedom that Halo 2 offers but the reason we like that freedom is that if we ever need something more fancy we know that we can sort of add it to our base components cool and my last question is what are you using Halo 2 ECC for yeah so we're building a new project called Axiom which is a trusses indexer which allows you to take any facts a historic fact from ethereum and prove it on chain for use in your smart contract cool thanks he