ZK8: A New ZK Nullifier Signature for ECDSA - Aayush Gupta - 0xPARC

Transcript

foreign and like I said please if you if you decide to leave please keep the conversation to a minimum back in the hallway otherwise uh please welcome ayush cool thank you so imagine you have a selection of these applications for instance maybe a zero knowledge airdrop where you want to have Anonymous governance where people aren't influenced by seeing other people's votes in order to do this you need to airdrop tokens to an unlinked account unrelated to people's eligible account and then have them vote from there

however you have to ensure that there's some signal that avoids people from double claiming this airdrop even though they're completely anonymous similarly maybe you have a message board in which you have these heated back and forth threads and you want to make sure that if someone is both the poster of a thread or reply to the thread and they want to reveal oh I replied up here and up here and I posted this thread in order to have this correlation inside the thread you need again some notion of unique pseudonymity where the person even if they're Anonymous can say I'm the same person in this other post or consider Anonymous voting if you have an anonymity set that you want to allow to vote on a protocol but you want to make sure that no one's double voted

again you need some signal that says hey I voted in the past so don't let me vote again in the future or any Anonymous application where you want civil resistance or uniqueness so after a bunch of discussion about how to do this we decided that the best way forward was a new zkanelifier scheme for ecdsa and the idea is that we achieve unique pseudonymity by creating a new signature scheme that's very easy to put in a ZK snark that allows you to verify that you are in fact a unique account and the work was done with Kobe AJ locksman from Xerox Park and MIT along with a ton of input from some other folks so let's try to think about what exactly the signal we want like what the

properties are so the first thing is we need it to be unique um if we have this kind of nullifier we want to make sure that each person has a completely different value that they can input at the same time it has to be deterministic if you want to prevent something like double voting or double claiming it has to be the case that each person can only generate one such Identity or nullifier we also need it to be verifiable without users copy pasting their private key all over the place this allows compatibility with secure enclaves and Hardware wallets where people can't even remove the hardware key from the hardware wallet and the final things that we want this nullifier to be non-interactive if you've heard of nullifiers before you

might have heard of something like tornado cash or semaphore in which people sign up register their nullifier and then the anonymity set is limited by the people who have signed up before you so for instance in tornado cash in order to be completely Anonymous you have to wait a certain number of people to withdraw before you and then you can withdraw and this is because the security is limited by a much smaller anonymity set than the full anonymity set similarly with semaphore the anonymity is limited to all the people who have signed up for some before before you but the reason we don't want this interactivity like turn your capture summary forward because we want the power of the full anonymity set to begin with the very first person to vote should have no less anonymity than every other person who votes or interacts with

the protocol so let's try to go through some ideas that maybe will or won't work and try to think what possible function could we use as this unique deterministic Anonymous identifier one idea is deterministic ecdsa signatures uh you might have noticed that if you sign something in in any wallet in ethereum it'll appear the same every time so what if for a nullifier we got a deterministic signature of say the app name and we hash this and use it as our nullifier uh and this is how we verified that someone couldn't double claim or double vote because their half should be the same every time they try to interact with the protocol now the issue with this although it might seem good is that while wallets Implement deterministic signatures a user could take their own private key out and Implement a

non-deterministic ecdsa signature where they just generate the randomness randomly and for us to verify whether or not they've used deterministic or non-deterministic signatures we need their private key in order to verify that the ramnets are generated correctly and so it's actually not possible to verify this deterministic ecdsa signatures determinism without the private key and that breaks the third property that we wanted is that we don't want uh we don't want the user to have to input their private key there is this idea in the literature of like vrfs or vufs or deterministic signatures and you can imagine that maybe this would have the properties that we want but the issue is that almost all of the vus and literature and almost all the unique signatures in the literature aren't compatible with ecdsa uh as it's implemented on ethereum and

Bitcoin Etc and the curves that they're on are different than SEC p256 K1 so it's it's actually not possible to use any of these algorithms as they exist on ethereum another idea you can think of is maybe we can hash uh the message which in this case would be the app ID or the thread ID and our public key and this can be the user's nullifier so they post this and they say okay because uh if I interact with this protocol from the same public key again in the future this value will be the same uh now the issue with this is that it kind of looks to have all the properties we want on the surface it is unique it's deterministic you don't need the public key you don't need the private key and it's not interactive but the issue is that this breaks anonymity

because there's only 300 to 400 million public keys on ethereum and so anyone could go through all these public keys and calculate this hash for every single public key and then match it to the nullifier and completely de-anonymize who they are with a CPU amount of computing power and so while this seems secure it's not quite what we want okay maybe instead of the public key we can use something like the secret key where okay this is still a unique deterministic uh verifiable and and it's not and it kind of don't need interactivity to generate this but again the issue with this is that you can't verify this without the secret key because you're calculating it inside of a hash um and so this is also sort of there but not quite

and it turns out that the final answer is we use the hash of the message to the power of public key has a message comma public key to the power of secret key kind of combining a lot of the previous ideas and in the literature this is called like a ddh vrf and the idea is that this gives us all the properties we want it's Unique deterministic non-interactive and while it might seem like you need a secret key to verify this we actually came up with the algorithm where you don't need the secret key to verify this was calculated correctly so maybe to summarize kind of the properties that we want in this nullifier so far the idea is that we want this deterministic function of a user's secret key that can be verified with only their public key yet keeps them anonymous and the idea is that the way this would

keep them Anonymous is that we can do this verification with the public key inside of a ZK snark so to be more concrete about what exactly we're doing here I'll try to walk through briefly the intuition behind the math that we use to actually verify the signature algorithm I've tried to color code all the different signals here so you can kind of try to link what different things are but it'll probably be a little bit dense so I'll just try to give the high level intuition so you remember that our nullifier was the hash of message come a public key to the power secret key and inside the secure Enclave so this would be inside the wallet uh either the software wallet or the hardware wallet it would just calculate a couple of these signals and you notice these are very easy for a hardware wallet to

calculate things like hashes and exponentiation are possible to do inside 40 kilobytes of memory versus more complicated Expressions usually aren't and the idea behind this is that this C value functions almost like a kind of a Fiat Shamir hash where the idea is that because you calculate this hash and you have the C value everything inside of the hash must have been calculated before the value of c and so when we publish this s value from inside the wallet the idea is that the randomness was committed to before you calculated C because it's inside the hash and thus and also the secret key was committed to because you committed to the public key and so it's the case that you must have had the randomness in the secret key before you calculated C and thus the user must own the secret key and this

owns the account the idea is that we can then once these signals have been output by the wallet so the nullifier and these two additional values inside a ZK snark we can just verify that in fact these values are calculated correctly and this verifies in fact that the user is who they claim to be and that this nullifier was calculated correctly now the other thing that the snark has to do which will be application specific is both verify the signature and nullifier and that whatever they were going to verify this Mark anyway so for instance maybe you want to do an airdrop or a voting protocol so you want to ensure that the public key is in the anonymity set and this would also be done by the protocol sure yeah so it's a great question so why

can't we just use a pairing to verify the discrete law was calculated correctly and the issue with the pairing is that pairing only work on Curves in which ddh is easy and the issue is at SEC p256k1 which is the curve that Bitcoin and ethereum use pairings aren't possible on the native curve itself because ddh is hard um but it's a good question like this it kind of alludes to the case why we need a new signature scheme instead of using existing schemes that already uh are in practice now one interesting thing that we discovered while doing this work is that while this seems like a Panacea there is one imported trade-off that we are making which is quantum post secrecy now

on one side we have semaphore or tomato cache in which case the nullifier is calculated using hashes and even 100 years into the future or maybe never depending on your stance um if a quantum computer came along that could break Bitcoin and ethereum key pairs your semaphore and channel cache anonymity would still be safe because no one will be able to undo your hash but for us uh we trade off this non-interactivity and the issue that we take is that as a result a quantum computer that can break ethereum and Bitcoin key pairs can then also break the anonymity of someone using our nullifier scheme what they would do is they would just take the discrete log of all the ethereum public keys they would

calculate all the secret keys and they would calculate all the resulting nullifiers and again do a similar matchup where they look at your nullifier and see which person you were now it's kind of an open question whether or not this is something we need to worry about the projections of when quantum computers that can do this are going to appear ranges from 2050 to 2100 to never because of noise limitations but it turns out that any deterministic function of the private key will have the exact same issue where a future Quantum adversary can break past anonymity and it's kind of interesting because the rest of ethereum or Bitcoin is completely secure the idea is that ethereum you can just have users sign their Quantum secure key pair once Quantum adversaries become a real threat

and the entire network can seamlessly transition to a Quantum proof system and all the funds are safe I'll pass zero knowledge proofs also maintain anonymity because they're statistically zero knowledge but this is the one thing that would leak anonymity and you can kind of try to think of ideas where we can have a nullifier that works the way we wanted to but is not a deterministic function the secret key and the issue with this is that this requires a user remember some external information like a password or a secret or another secret key um and the issue with this is that it would no longer be a deterministic nullifier of that account so it's kind of interesting to think about all the different ways that

Quantum adversaries could deal with zero knowledge and the systems that we create and to do that we have like a brief mental model that describes our how Quantum oracles can break ecdsa that you can find on the slide link that I'll post at the end now there's a bunch of interesting future research approaches that might be interesting to explore for other ways to do these nullifiers and I've put a couple here um the idea is that maybe we could do function of the seed phrase to have a different nullifier maybe we could keep everyone's enemy secret until the enemy pool is big enough um we could try to link it with a Quantum resistant key pair although this isn't currently possible with ethereum and we could try to use something like a rate limiting nullifier or if someone tried to interact with the protocol twice it would leak their secret key

and the idea is that this ddh vrf can also be used for this kind of deterministic anonymity Elsewhere on chain it's kind of interesting to think about all the different ways that this nullifier could be used even Beyond just pseudonymous applications so in order to ensure that our scheme is actually secure because we're implementing it in wallets we published a full paper where we have a very rigorous cryptographic proofs of all the properties that we want to show and the way these cryptographic proofs work on a high level is that we generally show that if we can break one of these properties then we can break the security of diffie-hellman which we're quite confident is secure we also have a blog post because helping folks understand this notion of pseudonymity or nullifiers can be like a fairly uphill task and so we wanted to

make this accessible to people who are just reading posts and not papers and finally we have a proof of concept for what a wallet implementation could look like and we're going to try to work on implementing it into metamask and burner wallet very soon um and also creating ERC and EIP so people can have like a standard for which to build off of and uh additionally we want to make sure that we can add an appendix to this specific RFC for ddh vrf so that again is standardized across like all applications that we'll be using section 256 K1 as our base curve cool so if you want to see our repository with a link to the slides the paper or any other information in this presentation you can go to this QR code and if you have any questions feel free to meet me outside or DM me on Twitter

cool yeah of course I'm happy to take questions if anyone has any cool uh does anybody in the audience want okay cool we'll start up here uh I uh thank you for the presentation uh can you please elaborate more on the fact that um why deterministic SDC signature cannot be used as nudifier yeah so in the beginning I mentioned that um there's right so the idea is that the way the deterministic ecdsa signature works is it's effectively identical to a non-deterministic ecdsa signature except you see the randomness using the private key and so what someone could do is they could generate a non-deterministic ecdsa

signature by just taking their private key using whatever Randomness they find you know from their PC and generating a non-deterministic signature that can change every time um but to know whether or not the user has done a deterministic on deterministic signature we need to know if they seated their Randomness correctly and so we need their secret key in order to verify that it was calculated correctly so this will require the user pasting their secret key into the ZK snark and would allow basically a break the properties that we want anything that clarifies it kind of admit this problem yeah so the question was uh

in theory could this work if we allowed users to input their private key into the ZK snark and the answer is yes that would work um if users kind of can copy paste our private key but we kind of think this is like a little bit of security vulnerability we don't want people like pasting their private key into an application and kind of just being like ah trust me like we're not going to do anything with it um and in addition for instance with Hardware wallets the secret key is inside the enclave and it's actually not possible to read that secret key um they have like a very specific security model where you can only read like signatures on the secret key and a couple of other allowed functions so it wouldn't even be possible for instance for anyone with a hardware wallet to interact with your

protocol which would be also fairly breaking we think yeah that's a great question other questions from anyone okay my my question I use what's your uh over under on quantum computers my guess is somewhere between 2100 and like 2200 I think it's like there's a lot of very and this is like a very like far off estimate like it's entirely possible in five years I'm like oh nope just kidding it's happening at this point instead but I think there's like a number of like theoretical limitations um both like the sheer number of qubits needed and like the vast amount of noise um even if it's the case that we can get

a quantum computer with like that a number of signal qubits that we need to break cryptography we would need like an order of magnitude more cubits just to like resolve all the noise um and so there's kind of this like theoretical question of like is it even possible to do this given like these like theoretical noise constraints um and given the rate at which computers are adding qubits every year uh it's going to take us like at least at that point to get it but if there's some like strange exponential increase that occurs in the middle uh then it's possible that we could get them faster but it also seems unlikely that quantum computers will come much faster because in between very simple quantum computers they can do very simple things and quantum computers with hundreds of thousands of qubits that could or you know several

tens of thousands of very good qubits that could break ecdsa there's kind of nothing in the middle like there's no reason for someone to develop a quantum computer with 1 000 really good qubits there isn't really like an application it's kind of called like the valley of death in Quant Computing and so it's kind of unclear like how we're going to incentivize like the sheer amount of funding that would be needed to fund this kind of quantum computer yeah go ahead okay how many gates is this knock circuit that I guess creates or validates this yeah it's a great question so because we're only calculating hashes and uh exponents of the elliptic curve it's fairly cheap it's like we think it's like around 100 000 constraints but we

think we can optimize it a little bit to be like probably a little bit less awesome um final call for questions if not um let's all give ayush a hand [Applause]