Elliptic Curves, Pairings, and RSA in Circom, Applied ZK - Day 2

[Music] well thanks so much barry so today i'm going to be presenting with ye and stephen on various projects we have to implement cryptographic primitives in snarks specifically in sircom for growth 16. stephen unfortunately couldn't be here today for coveted related reasons so he has a recording that he's been kind enough to share with us about double blind which is an rsa circom project and an associated set of tools and demos cool so let's get started the first question here is why bother there's a bunch of questions uh around why even do this as we are moving away from groth 16 and as we are moving towards more snark friendly cryptographic functions uh it seems like this is sort of you know an attempt to live in the past but you know there's a number of important reasons why uh this kind of stuff is important um the first reason i would say is that you know today with snarks and this isn't something that's necessarily specific to which proving system we're using or what cryptographic primitives we're implementing one of the key sort of framings that we have around what snarks enable us to do is that they give us an expressive language for claims so what does that actually mean well we see zk snarks very much as you know something that falls under this category of quote programmable cryptography i.e tools that turn math problems into programming tasks rather than having to use special purpose-built cryptographic tools we now have these programming languages that allow us to define circuits compose arbitrary claims and primitives together uh things like you know i know a secret uh that like uh you know is behind one of these commitments or behind this particular commitment or uh which has like certain guarantees around certain commitments um and instead of needing to go to a cryptographer and ask them to build a new special purpose math protocol for us we can instead write circuit code so here's one example membership proofs we're finding are likely to be increasingly important as we move towards a lot of these new zk-enabled apps and to give an example of the flexibility that snarks provide over previous primitives that we've had for membership proofs i'm going to present a series a series of claims so the first claim and one that has underlied a lot of internet infrastructure for many decades now is the simple claim i know a private key corresponding to alice's public key we have protocols that do this quite well we have key registries that you know a lot of people are now on uh and this is something that's been around for a while and it's been very useful uh and it's something that um you know we have we're very well equipped to do prior to uh these sorts of programmable cryptography tools such as snarks okay so a slightly harder claim is the claim i know a private key corresponding to alice bob or charlie's public keys this is something that is sometimes known as a group signature or rings or a ring signature and while protocols for proving claims like this have existed for a while it unfortunately is the case that uh oftentimes they're not super compatible with the protocols and registries we have for people who make this kind of claim meaning that you know you don't you aren't able to move between these two claims in the same system you need to bootstrap an entirely new identity registry uh an entirely new infrastructure in order to be able to have a system that allows you to make both of these types of claims in a snark however this turns out to be really simple if you've got the cryptographic primitives implemented for this inside of a snark you can simply write a circuit that asserts that you know i'm going to make a commitment that is equal to a key generation function evaluated on a secret that commitment when compared against the set of commitments that i want to prove that i know one of the secrets to via this polynomial evaluates to zero and then you know i can generate message attestations that might bind me to all sorts of things okay slightly harder than this is i know a private key corresponding to alice bob or charlie's public keys and depending on some you know perhaps configuration flag or some uh you know in protocol configuration uh the other two who did not sign this either can or cannot disavow this message um so once we get into this territory we see things like you know there's all sorts of papers that propose different mathematical schemes for group or ring-like signatures that allow you to either like post facto prove that you did or didn't sign the message with snarks however this is super easy you can simply you know take this circuit pseudocode and do things like add assault so that way it's very hard to deny that you don't know some salt which would when combined with your private key generates the message attestation uh and then we get to more elaborate claims like this i know a private key corresponding to alice bob or charlie's public key and i either possess a signed attestation from one of david eve or fred these identity attesters who are trusted or during the block with header x i knew the private key corresponding to an account with at least 32 eth and and you know you can imagine like a bunch more predicates like this so once we get into this kind of territory uh we now clearly need kind of an expressive language for these sorts of claims we can't rely on going to a cryptographer and asking hey can i get a zero knowledge protocol for this um that's something that is simply not feasible and again it's ideal if the protocols or strategies that we have for making these or for proving these kinds of claims uh are also allowing us to live in the same system with the same key registries where i'm making these kinds of claims as well okay so the second reason to specifically implement these existing primitives like ecdsa or standard hash functions into uh zk snarks is so that we can bootstrap off of existing data sets so um i want to kind of you know illustrate the dichotomy here between two ideas there's the idea of snark friendly cryptographic primitives and then there's the idea of snark compatible cryptographic primitives at least in the near term our most widely used cryptographic systems will not be snark friendly by snark friendly what i basically mean is you know things like commitment schemes or signature schemes or things like that that are specifically very performant to implement inside of a snark existing data sets um oftentimes rely on cryptography which was built out before snark constructions were even known and so at least for the foreseeable future if we want to use like existing you know identity registries or other data inside snarks inside our expressive identity language we're simply going to need to uh do the hard work of implementing these primitives inside of snarks so for example you know when i when we speak about like key distribution or identity registries like gpg or you know ssh we have these like large basically registries of things like rsa keys that now exist out in the wild that we could be making claims about uh if we can get those into snarks and there's been a lot of there's there's some overlap as well here with folks working on zk evm related work where we're also interested in implementing ecdsa keys because you see dsa algorithms inside of snarks because that would enable us to make uh these expressive claims about on-chain data uh and about on-chain identity sets um so yeah snark friendly might mean that uh you know this particular primitive is very well uh is very performant inside of a snark but at the very least we can kind of aim for four primitives that are commonly used today making them snark compatible by building out a standard set or a nice and optimized and easy to use set of libraries and once we've done that we can see what applications we can build okay so a few more notes on uh our approach in general how we're thinking about where these primitives fit into a larger context and why we implement them in cert common with groth 16. um so there's a couple of things that we aim to do at xerox park and with this particular like primitives implementation project so the first the first thing that we always do is we try to target useful uh end user facing applications so for example many of the applications you saw yesterday such as stealth drop private air drops these are things that can be concretely useful to users you can imagine even as early as like today double blind which allows for rsa group signatures as well could allow you to build like message boards within a github organization and that's a concrete use case you can imagine today so we target an end user facing application and then we actually try to build it out end to end and what we found is that currently the you know tool stack that has um you know that's kind of the most stable uh and the most easy to use end to end all the way to the point of having a user in browser being able to generate a proof and participate in the protocol um is sir common snark js and you know we do additional work like what uh lockman and uma were talking about yesterday with metamask snaps to you know really try to close the gap between these ideas being like these theoretically interesting ideas and these actual proof of concept prototypes you can physically play with the other thing that we focus around is just get something working to begin with and then optimize so some of the circuits we'll show today are like super expensive and can only be basically proofs can only be generated on a dedicated proving server but we're okay with this for now and we're okay with sort of having these like shadow like back ends because we anticipate that as uh you know we move to better proving systems or as we continue to optimize circuits or as libraries get better or eventually as hardware gets better uh like this will be a very solvable problem i think even with like circumstance.js like three years ago uh the like performance accessible to you know your average zk developer was probably like two orders of magnitude worse so you can kind of imagine that things are going to keep getting better and then along the way in actually holding ourselves to implementing an end user facing application end to end we're going to uncover engineering and design challenges so for example like this is what motivated the metamask snaps work this is what motivated uh nalin and blaine and kevin's work on like chunked z keys it's something that's that makes things like delegated proving really exciting and yeah so we aim to make existing cryptography at least snark compatible uh to see what can be built uh and in doing so we can create this feedback loop between applications and infrastructure so we can understand like what really are the next bottlenecks to snark apps getting into production okay so first i'm going to talk a little bit about sircom ecdsa which is a set of circuits that we published and have been optimizing for the last couple of months so the idea here is we basically want to implement ecdsa key generation and signature verification in snarks and currently we have a priv to pub circuit that takes a private key and proves that it takes a secret private key and proves that it is the pre-image of the ecdsa pubkey gen function and that works in under 100k constraints and we also have ecdsa signature verification and 1.

5 million constraints and you can check out those circuits as well as a number of useful utilities and demos on our circom ecdsa library on xerox park github organization one thing i'll note is that these circuits are certainly not production grade they haven't been audited they haven't been you know we haven't really been able to run like verification tools on them uh so this is very experimental and again like the goal here is proof of concept applications not necessarily you know i i don't think these are fit for production or there will be at least like a number of you know pretty substantial additional steps we'll need to take um here are some benchmarks uh you can see that the pub key gen function or the pubkey gen circuit is 95k grot 16 constraints um and uh unfortunately the proving keys are pretty big um so that's another kind of one of the limitations to to putting these into apps but we have a number of workarounds for this kind of stuff a few of the challenges that we encountered in implementing ecdsa was uh you know the first thing was we had to build out a pretty robust set of big int arithmetic techniques we do slightly different techniques from what aztec and as i'm aware like a few of the other teams are doing for their big int implementations uh we also do a number of curve specific optimizations around the fact that we're working with the secp 256k1 curve where the you know like underlying field is very close to two to the 256. um there's a couple of subtleties with ecdsa uh and then one of the next things that's really important here is figuring out like audits or ideally sort of some sort of like verification of correctness of at least different sub components of these circuits so we're going to be me and yi will be speaking about this uh in an afternoon workshop at 1 30 if you want to come and learn about some of the trickier like optimization techniques that we are using and hopefully some of them may also be applicable to plonk like systems yeah so a couple of applications we saw stealth drop yesterday which allows you to do air drops that to addresses that can't be linked to the original address in the whitelisted set uh additionally you could imagine like things like message boards and we have this is a zk message board it's not one with ecdsa integrated into it but it sort of demonstrates how one might build an anon build an anonymous message board that allows you to prove membership in a group and you can imagine like on-chain identity sets with either zka tester or some other you know infrastructure that allows you to construct sets and make claims such as iheld x tokens at least x tokens at y time or like i am the owner of one of this nft collection set things like that okay so next we're gonna show double blind which is a project from steven who couldn't be here today so we have a video from him hey everyone today i'm going to show you an application we built called double blind double blind is an off chain application that allows anyone with an rsa key to anonymously sign messages on behalf of a group let me show you how it works first let's open up the page and type message does anyone else think we should switch to three space indentation um this is a potentially controversial message and it's the message we're going to anonymously sign today to do that we need to define the group that we are signing on behalf of by listening to group public keys so let's include our friend vitalik who his public key i have pulled up and also ourselves because we need to do that to be able to sign as this group finally let's enable the secret identity feature um this is uh this gives us a masked identity which is like a username of an anonymous account that we control and post under this will be important later on if we want to prove that we were the author of this message or link multiple of our messages together we are now ready to generate the group signature when i click the sign button the application starts computing a zero knowledge proof using the snark js library the zk snark proof is computed by evaluating a custom circum circuit that verifies the constraints for authentication and authorization while keeping my identity and secret keys private it usually takes around 30 seconds and results in a succinct string that is easily shareable here's a string now i'm going to take a brief detour from the demo to explain how the circuit works first the circuit authorizes me to sign for the group by validating that my public rsa key is included in the list of authorized keys this validation is done by checking a local inclusion proof that my public key is a leaf of a given verbal root while the merkle root is treated as a public input the merkle proof itself and my public key are private to preserve anonymity in parallel the circuit authenticates me by verifying a signature that was generated using my private rsa key this is what we call the double blind key and it's sufficient to act as my login credentials the signature was generated using this terminal command i'm highlighting and enter into the app via this text box note that i never needed to paste my rsa private key into the application this is consistent with best practices for safely handling private keys the signature is another input to the circuit but it's kept private for obvious reasons you can find a link to this diagram that i'm using here as well as more details in our docs page now back to the demo we have our group signature and it's time to share it with others so that they can verify it and read the message i can do this in any number of ways email it to people from a throwaway email account post it to the blockchain anonymously or put it as a response to google form or google doc let me show you what it looks like when someone is given the verification link when they click this link they are taken to a page where the signature is pre-filled but the message and public keys are blank all they have to do now is click this verify button the message masked identity and group parameters are decoded and the zk proof is verified so let's talk about who can use this tool if you've used ssh or github before you probably already have an ssh key pair and that's all you need to use this tool additionally you can grab someone else's public key like i did here just using github by adding dot keys to the end of the url this is why we chose rsa over other asymmetric encryption schemes it is the most widely adopted one today and has great key distribution registries like github and therefore it's ready to integrate with all the existing web 2 cryptography rails so let's say you're interested and you want to use double blind to for example hold a survey for your github organization you want everyone in the org to be able to vote anonymously while preventing anyone from from voting twice all you need to do is grab the public keys of every member of the organization and input it into the app then share a link to the pre-filled signature generation form like this one your organization members will need to first authenticate by running this terminal command and pasting the signature into the box then they'll be ready to sign and all they have to do is input the message and click sign all the signatures you collect this way can be verified and shared in a decentralized and transparent way making for a trustless survey process that all participants can help validate you can also use this to power other authenticated but anonymous communication systems like communicate community gated message boards whistleblower hotlines or feedback forms of course this is just the beginning and there are infinitely more possibilities both on and off chain to close i wanted to i wanted to share somewhat sobering thoughts like any technological innovation ckrsa group signatures can be used in both good and bad ways for example the fact that you can be included as a member of someone else's group without your consent can be scary and we were thinking hard about affordances of this tech so if you have any thoughts on the matter we would love to hear from you you can try out the app at double blind dot xyz and contact us via github or email thank you for listening oh does this work okay cool yeah and just to to summarize uh we have rsa signature verification in circom uh and about 300k constraints for grout 16. um we're building out infrastructure for uh uh building and serving accumulator routes and you can find the group signature utility at double dash blind dot xyz and if folks are interested in following up i can share steven and andrew's contact uh info after the talk now i will turn it over to yi who will be talking about zk pairing okay so as ryan mentioned i'm going to present our work on implementing different types of elliptic curve pairings as well as bls signature verification in cerncom in gross 16. and i should mention that this project was really spearheaded by jonathan wang and vince vincent wang who unfortunately can't be here today so to summarize we've implemented uh pairings on the curve bls 12 381 which is the curve used in eth2 for bls signatures so we have implementations of the optimal eight pairing in a little over 11 million constraints and the bls signature verification in the case where the pub key is in g1 and about 19 million constraints so give a little bit more detail on what that means cryptographically to verify a bls signature you have to compute a single pairing check namely that the pairing of a base point g with your signature is equal to the pairing of the public key associated with signature and a hash of the message so i'm going to give a brief demo to concretely verify this in for a specific signature taken from the eth2 beacon chain a couple days ago so what we're going to do is we're going to take the signature of this validator on a block which you can look up the details of on beacon chain unfortunately the demo takes a bit of time so i'm going to x out of all these commands but what we're first going to do is look at the input we have an encoded version of the pub key the signature and the message hash for this block what we now do is generate the witness taking in this input let's imagine that two or three minutes pass and the witness has been generated then we're going to run the prover again imagine maybe one minute passes and it generates and if you believe me that i didn't just fake those last two steps in about one second you'll see that the proof verified okay now back to the presentation um if you have more time you can try this for yourself okay so some benchmarks on what's in principle happened there uh we have three circuits we have bls verification the optimal eight pairing on the bls 12381 curve and the tape pairing which is not really used in production but just a demo of a larger pairing you can see the number of constraints is quite large so these are pretty big circuits that require very beefy servers to run the ram constraint is over 100 gigabytes for all of these circuits and as you can see the witness generation and proving times are pretty long even with a very beefy aws machine and last thing to mention is that here even the proving key sizes are in the gigabytes so that's definitely a constraint for applications okay so let me just give you a brief overview of the challenges involved in implementing these circuits so as a quick refresher the to implement the optimal eight pairing you there's two steps for the answer for the pairing is this quantity f sub q of p it doesn't really matter what it is but it ends up being an element in a finite field one has to first compute this quantity f and then raise it to a very large exponent q to the 12 minus one over r that's a little over 4000 bit number so to compute f sub q of p we implemented miller's algorithm within sircom there's a couple challenges to resolve to do that first we need to use big integer arithmetic over a non-native field and for that we use similar techniques to what was used in surcom ecdsa and we'll talk over those in detail during my workshop with brian this afternoon secondly we needed to do elliptic curve arithmetic over a field extension rather than the native field itself so that introduces another layer of mostly software engineering complication and finally we needed to implement all the traditional cryptographic optimizations for miller's algorithm but within circom so again this is a lot of engineering work the second piece is what's called the final exponentiation so that turns out to be a 4316 bit exponentiation over the finite field extension fq12 q is a 381-bit prime so again in the traditional cryptography literature there's a bunch of optimizations where first you can do exponentiation to q using what's called the action of the frobenius which is very cheap although a little bit complicated to implement in circom and second we have to handle the remaining exponentiation by compressing to what's called a cycloatomic subgroup so even in you know a traditional programming language like javascript or python this is quite complicated but we ended up having to do this in circle you can look at our github if you want to see the details the last thing is to extend from optimal 8 pairing to actual bls signature verification there's one last step which is hashing your message to an element of your elliptic curve group it turns out if you go read the spec that this is a pretty complicated operation i've drawn a little diagram of how it works you start with your string you do these five operations each of which involve some elliptic curve path in the end you end up with a point in your elliptic curve group g2 we want to investigate how to do this on chain since we didn't want to snark it and we found out that actually this is extremely expensive and uses a lot of gas so for perhaps the first time i've ever experienced we found that it was easier to just put this within circom and put it in a stark so that's what we've done and in the code on our github you can see that we we basically put the entire process of bls verification after hashing to a finite field element within the snark so you can check out our repo which i just made public this morning and we're going to have a more fully featured demo site up at zkxzk.xyz soon thanks and bryana are happy to take any questions um yeah i'm curious for the uh optimal aid pairing on vls12381 which uh optimizations and engineering tricks are transferable to bn254 and or can we just kind of like use the same stuffs and just like on that curve as well yes um although the current circuits are specific to bls-1231 um they can be changed to any other curve with some very minimal changes almost all the optimizations will flow through directly we just need to change the underlying elliptic curve library a little bit uh yeah just acting as a parrot here my colleague was watching the stream and would like to ask a question so uh yeah my colleague believed that the main benefit of supporting pairing is to allow for recursive proofs so you know do you have some measurements and number of constraints for verifying a proof recursively it's curious uh that's next up on our roadmap but we just haven't implemented it yet so just for some context to verify recursive proof you have to do a pairing check that involves evaluating four parents and so we'll let you know when we have those benchmarks hi what approach are you using for non-native field operations um we'll be discussing this more in our afternoon workshop but the basic idea is that you know we break up the uh 200 or in the case of like ecdsa where we're working with 256 bit numbers we break it up into 64-bit limbs uh and then we use a variety of intermediate representations that are a little bit more snark-friendly to do most of the like big into operations like additions and multiplications uh and then afterwards we pull out of the intermediate representation into this you know standard representation of these elliptic curve points so we'll talk a little bit more about those representations and why why operations are easier in them later today do you see a path towards breaking down the big circuit into several smaller circuits to make it more accessible to a smaller machine and maybe unlock distributed proofing i think the constraint for that is the cost of recursive verification which in our case is actually quite expensive so i think for circuits that are even larger than the ones that we're talking about already that could be a path forward but for breaking these down it's not clear to me that you can gain so much yeah at least one thing that this does is it establishes kind of an upper bound on the largest circuit you should ever have to prove assuming that you have access to some sort of like you know multiple machines or proving servers and so you can imagine as this stuff gets better like eventually we'll probably move to something more like plonk like uh and you know there's lots of circuit optimizations to be done the proving libraries can presumably be optimized and hardware can presumably be optimized so uh for like because this is like a generic non-native field implementation of pairing it can sort of serve as like an upper bound on just like the biggest snark you'll ever need to do hopefully thank you kind of a follow-up question so uh another benefit of pairing is one can build a universal dynamic uh accumulator and i was wondering if there's any experimentation on that front thank you uh again that's something we're interested in doing but we haven't gotten to it so we'll let you know i have the impression that um for cryptographic primitives uh it's mostly kind of grinding and not so much using lots of memory and i o but you said 100 gig of ram was required for this machine so is it the case that for these big proofs you do need a lot of like very fast local very near kind of memory um i guess i'm not sure about the local memory but the reason for the ram usage is just that these circuits have a large number of constraints and a large number of inputs and so the memory usage is basically determined by those in the graph all steps of graph 16 so the proving the key generation and the circuit compilation [Music] you