Non-interactive, Unique Nullifiers: The Key to The Next Era of ZK by Aayush Gupta

foreign [Music] knowledge airdrop in which you enable Anonymous governance where people's votes aren't impacted by other people's votes where people can vote independently and they're only revealed once you want to tally the votes or once the voting period is over in order to do this to do a zero knowledge airdrop you need a way to avoid double claiming that is people can anonymously claim their tokens to an unlinked account but still there's some identifier that represents them that prevents them from claiming the same airdrop twice or maybe we want to do an anonymous Message Board in which we know that each of the people cannot be identified but we know for instance that maybe the first poster is the same as the third poster or imagine we want to do Anonymous voting within a large anonymity set such that the very first person to vote has the full power of every single person in this anonymity set or really any civil resistant Anonymous application so we thought about what we could use to be this kind of tool that stops us from double spending and it's kind of unique identifier of someone on chain and after talking a bunch on Discord we decided to create a new Zeke nullifier scheme on ecdsa this is Joint work with Persona Labs geometry research and originally done at Xerox Park and MIT so to kind of clarify what exactly this nullifier is let's try to maybe go through some properties so if you want to avoid people from double spending and we want each person to claim only once then we need this property this this identifier outputted by this account to be unique that is everyone should have a different one we also want this value to be deterministic that is if I have some ethereum public-private key pair I should only be able to generate one of these signals finally the signal I generate should be verifiable without access to my secret key this is because in a ledger wallet or in a secure Enclave it's not possible to even read the secret key or take it out of the secure Enclave we also don't want users copy pasting their private Keys all over the place and finally we want this number this scheme to be completely non-interactive if you've heard of nullifiers before you might have heard of something like tornado cache or semaphore and the way that works is that as people sign up the anonymity set grows bigger and bigger and bigger however the first person to use tornado cash or the first person to sign up for a semaphore group has zero anonymity until more people join but if we want the full power of the entire anonymity set for the very first person we need the scheme to be non-interactive that is there shouldn't be two phases like a sign up phase and a utility phase so to understand these properties a little bit more one useful exercise is to go through some examples of schemes that may work or may not work so imagine when we wanted someone to post this deterministic value that identified themselves that stop them from double claiming or stop them from double voting but they use the hash of a deterministic ecdsa signature now you might guess that this has all the properties we want it's Unique if you're signing a message a deterministic signature there should only be one um it's it's uh non-interactive anyone could generate a signature and blend into the anonymity Set uh you don't need people to to interact and sign up for the scheme first however the issue of determines the ecdsa signatures is that you cannot verify that a deterministic ecdsa signature was generated with the correct deterministic Randomness unless you have access to the private key that is deterministic EC Dasa signatures are identical to non-deterministic ecdsa signatures because the randomness is like the hash of the private key and so if you're trying to verify this on chain or in a ZK snark you would need the private key so it doesn't quite achieve what we want it to achieve a second idea is this idea called a verifiable unpredictable function or a unique signature now the vast majority of the schemes for these are on pairing friendly curves and ethereum which is on ecgsa on SEC B 256 K1 is not a pairing friendly curve so the vast majority of this literature is fairly inaccessible to us we could try something like hash of message from a public key you'd imagine this is unique every account every public key has a different value of this hash it's deterministic if you have a public key and there's some message say the app ID then this hash is deterministic it's verifiable without your private key and it's not interactive you can give this hash without signing up in advance now the issue with this is that it's a little bit subtle but it's actually possible to de-anonymize people who are using this for anonymity the way you do that is you can take the list of all 200 400 million private keys on ethereum calculate the hash values for every single one and match it up with this nullifier value on chain and boom you've de-anonymized a person who tried to use this as their unique identifier maybe kind of getting inspired by this we can try something like hash of message comma secret key you'd imagine this is similar to the the public key case except you can't take everyone's secret key on chain because you don't know everyone's secret key so it's not possible to anonymize people in the same way but the issue is to verify something that's behind a hash you have to calculate the entire hash function inside the xero knowledge proof or inside whatever identity primitive you're using and we don't want to use this copy around the secret key and so this scheme isn't quite it so finally we resolved on this scheme we use a hash of message from a public key to the power of secret key it's kind of similar to the other schemes but it turns out it has this nice property that is a ddh vrf or a decisional diffie-hellman verifiable random function and specifically what this means is that we can verify that this is actually calculated correctly without access to the secret key so to maybe summarize like what exactly the properties we are that we want so far is that we want this deterministic function of a user's secret key that can be verified with only their public key and keeps them anonymous and the way we do this is we Define a new deterministic signature scheme on ethereum so I'm going to try to go through what exactly the signature scheme is and so this is going to get a little bit Mappy and I've tried to slightly color code the numbers that are the same so you can kind of correlate them across um and although the math is a little bit difficult to understand on first glance I'll try to give you an intuition for why it achieves the properties that we wanted to achieve so remember our nullifier was the hash of message from a public key to the power of secret key and so this value will be public it will be calculated inside the user's wallet whether it's our metamask or their Ledger or anything else and this value will stay public the entire time it will be posted on chain eventually for everyone to see these private outputs will be created by the wallet and given to the user these outputs if they were seen by the external world could de-anonymize a user for instance if you saw their public key you would obviously know who they are um and so the idea is that these signals are kept to the user and the user can use them to generate a ZK snark so what the user does is once they have these signals you can think of this as splitting the signature scheme into a deterministic part the nullifier and the non-deterministic part the private part the verifier simply checks these values are calculated correctly now it's a little bit hard to drive through all this math so I'm going to try to give like a high level overview of why we have this kind of C value floating around now the reason we have this like C value floating around is that when you're taking a hash it's impossible to Brute Force the output of the hash so you must know all the inputs that went into the hash this means that the person you can kind of think of this C commitment as a hash commitment to these values of G to the r to another fire to our public key then we calculate this value which is s which is based on the C value which we know must have been calculated after c and notice that this s value does not reveal the user's secret key although it has secret key in it it's blinded by a completely random number the check in the snark you'll also notice has no secret keys in it we only pass in these signals none of which you can use to derive the user's original secret key and the check that we do is effectively did the user calculate C in the correct order did they commit to their secret key their public key and calculate the signature in a way that would have actually proved that they owned that secret key and finally the ZK snark apart from checking that the nullifier was calculated correctly in a German succession um on the correct curve we also check whatever public key check we want to do this allows us to verify that the public key is in fact acting correctly and has some unique identifier but now I have to verify that the public key is in fact allowed to interact with this protocol maybe they're a numerical proof maybe they submit a Merkel try Patricia proof that they are they satisfy some condition on chain and the idea that we would also lump this in with the verifier check in the ZK snart so to summarize the wallet generates these signals the user plugs them into a ZK snark and posts the ZK snark when with a public nullifier output on chain proving that they are allowed to interact with this protocol and a unique user who is still going to be kept Anonymous now interestingly when we were doing this work we discovered this Quantum secrecy interactivity trade-off now it turns out that semaphore is extremely Quantum secure because it uses hashes but it's not it is interactive meaning that you have two phases and the first people interact they interact with the protocol have no anonymity our scheme on the other hand is fully non-interactive the very first person to use another fire will have the full anonymity of the entire anonymity set however it is not Quantum secure and the way that you can kind of think about Quantum adversaries in the situation is that a Quantum adversary can effectively take discrete log and prime factorizations but it can't undo hashes you can imagine that when we have a quantum computer with 2000 signal qubits that can break all of ethereum's uh public keys and derive their private keys in the actual situation of the chain continuing this is completely fine users can sign their new key with their old key before Quantum Supremacy occurs and the entire chain can move seamlessly to a new Quantum resistance system however if you can derive all the user secret Keys then if you remember the trick we did in the very beginning where we calculate the half of meshes come a public key for all the users and de-anonymize people we can do the exact same thing with this Quantum adversary calculated secret key Quantum adversary simply calculates every secret key for every private for every public key in ethereum calculates another Fires for every single one of these keys and matches them up with the anonymous signal and so interestingly any future Quantum adversary can break past anonymity um and the issue is that actually any deterministic nullifier scheme that has the properties that I defined in the beginning has its vulnerability because if you Source Randomness from only the secret key that means the quantum adversary can derive it as well and so you have to Source Randomness beyond the secret key which requires the user to remember that value which means you need to have a password so to kind of get a better intuition for like whether this actually matters or not there's the the predictions of quantum researchers very extremely widely some researchers have mentioned they think it's going to come as soon as 30 years signal qubits that can break ecdsa some researchers think somewhere around 100 years and some think that because of the noise problem it's theoretically impossible and it will never happen um it's a little unclear uh as of right now we have about 20 signal qubits and we need over 2000 to break ecdsa so I've written a short mental model that you can read once you look at the link on the slides which describes kind of how I think about this Quantum mental model of how these systems are going to evolve and whether or not we should be worried about it but I think for now the decision that we made is that it makes more sense to not be worried about Quantum oracles because as long as the protocols are transparent that you will be genomized in something between 30 and 100 years the idea is that most people probably won't care because by that time for instance even governments declassify their secret documents in this kind of time frame so to understand more how this another fire scheme is going and if you can use it yourself we have a paper in which we approved all the security properties of this nullifier scheme um we have a blog post that's going to be coming up on the Persona Labs blog soon and we also have a proof of concept uh in Rust and in a metamask snap finished um the next step is to put it into a ton of other wallets into Ledger into burner wallets into metamask core create an ERC standard for people to use this scheme so we can have unique anonymity across the board and to potentially write an appendix to an ietf RFC to make it a complete standard across all of cryptography if you're interested in seeing more about the code this link will link you to our GitHub repo where we have all the open source code we'll be linking to all the slides here as well along with the quantum mental model um and our Twitter if you want to learn more um you guys are interested in this uh want to use a scheme or are curious about uh student I'd be happy to talk and it would be really fun to see where the scheme can go if anyone has any questions about understanding the scheme or thoughts on where it can or can't be used I'd be happy to take any questions for the next five or ten minutes test okay how is this scheme called so right now the scheme is called just a ZK nullifier because we think this is the kind of most straightforward way to describe what is going on but I'm open to any other name suggestions I think there's a question in the front can you like explain uh probably maybe using an example how uh like this non-interactive uh is like is like seen in practice like in terms of like uh using the scheme like maybe like an airdrop like can you explain like how that system would work how like user would interact and like kind of maintain that property yeah that's a great question I can maybe go through the kind of the whole airdrop scheme and try to describe why it wouldn't be practical or something like that before but why it could be practical with something like the nullifier so if you imagine the semaphore scheme for the airdrop the way it would look is that people would first have to sign up to receive the airdrop and this is so people have to submit their semaphore commitment to some uh either like an on-chain directory or an off chain list and the issue with this is that people can then stable attack this airdrop very easily because they know that an interrupt is going to be coming and this is a way to gain eligibility for it and so because they have this two-step process people can spam whatever mechanism it is that they're using to determine who is legible and who is not resulting as being of somewhat impractical solution you can also imagine that if you didn't have a two-phase process where instead people could sign up for the summer for Keys whenever and claim whenever and the very first person to claimed the airdrop was sign up for this timer for key you would see only one semaphore key in the list of all summer Four Keys and then that person would clean their airdrop and so you would know that the person who posted that proof must have been the person who claimed the airdrop and so there's all the small anonymity set is is not ideal if you're trying to maintain perfect anonymity for everyone in the set with another fire scheme would work is that when you claim the airdrop you prove that you have another fire for a message like I am claiming the ZK airdrop and the verifier would prove that you in fact signed that message that you created your deterministic nullifier correctly and would allow you to clean the airdrop and then add that nullifier to a block list from ever claiming again and so what would happen is the very first person to claim no one would know who they are out of the entire set of all the keys that are eligible for the airdrop where does the like nft eventually end like it's an ethereum address versus uh like is it like the things are happening on chain or is like an off chain process or like uh just trying to understand that yeah that's a great question uh for those who don't hear the beginning the question was basically how does ZK airdrop actually implemented and the idea is that what you would do is you would prove that you own an account that is in the Merkle tree of eligible addresses for the SDK airdrop you would generate a summer for another fire for that scheme uh in the original case and then you would claim it to a completely unlinked unused account that has never had any transaction on ethereum um and then all the fire scheme you do a similar thing you would prove you have an account in this Merkel tree you would prove ownership of that account you would prove the nullifier Via this is another fire scheme and similarly the tokens would go to a completely new fresh ethereum account and there's no history on it and it's effectively anonymous that's a great question though yeah uh so just to expand on the previous question like a concrete example so you wanted to like airdrop an NF an nft to anyone who has a crypto Punk and but you want people to be able to claim it without revealing which Punk they are um within semaphore or anything that's like a two-step your anonymity set is only going to be the amount of people who like sign up for this mm4 and with this the anonymity even if it's just two people that end up claiming this nft they have the full anonymity set of like all all Punk holders if that makes sense and it's going to like a new address not to the one that has the punk hello all right uh so I'm wondering uh can you um expand a bit upon if you uh if you use this scheme for a uh sort of a multi-step protocol where it's not just maybe a tornado cache deposit and withdrawal or a claim scheme but you continue where you maybe have some sort of um transfer of private assets within the anonymity Set uh do you keep that anonymity and and how does that work yeah so the the way dark pool transfers would kind of work with its anonymity with this nullifier is that the way most people enter a dark pose they send their assets to like a specific smart contract and so you already know that the engine reset is limited to everyone who has ever interacted with a smart contract and one thing you could do is you could use something like semaphore and if you interact with smart contract the guarantee that you have to sign up for a semaphore key so because the anime set is already limited by something like an on-chain interaction the nullifier wouldn't add additional anonymity because it's already limited by the chain interactions however what it could do is prevent you from having to memorize secret notes so for instance with tornado cache you have to download a string and remember it forever um and if you lose that string then you lose your money but what you can do with this scheme is that instead of having to memorize a Toyota cache note you just remember the amount of money you got and then you could say okay I got one eighth so I'm going to sign a message saying here to cash one eth and I know that the nullify that it creates will be a valid note for my deposit and the contract can simply validate that and so it can help uh saving memory or losing strings for anonymous money but it wouldn't add significantly additional anonymity if the original scheme was implemented uh with the dark pool correctly ascending to the contract yeah that's a great question though hey hi uh okay uh I'm pretty sure like many of us would have read about nullifies for the first time in vitalik's article the one with like privacy applications now and like I did not understand it completely but I thought it was vitalik who wrote it so it must be true so so can you like just uh give a brief difference between that nullifier technique and your nullify technique for us to compare right uh so the nullifier technique that is classically referred to in mostly ZK snark posts um is another fire technique that exists which is uh kind of why Halo 2 defined a number of years ago and it's kind of evolved into being this semaphore type scheme in which another fire just represents that you can't double claim or double interact with a specific protocol because I know the fire nullify is their ability to do so um that is an added to a Smart contract or something and then when you interact with that in the future it would notice that you've already interact with it before and then stop that transaction from going through um so the scheme that likely is being referred to that in that post is likely a semaphore type scheme or a sign up type scheme in which this nullifier is like a hash or some string um which again would have to be interactively generated um and so when I when I say this kind of semaphore side or this like interactive side that's larger than the classical nullifier that I'm referring to yeah uh thank you for the talk um I had a general question um kind of about coming back to the example of the token get a job so if you either use like the zika nullifa or summer for to generate a proof um that an address is eligible for an outro based on um owning an nft in a set for example how does that respond to updates for example when you transfer the nft afterwards since the nullifier is only tied to the address could you then transfer that nft to different address and create another another file and again qualify for their job yes that's a great question so the way that you would solve this kind of multiple qualifying for the airdrop problem is that when you define when you release this airdrop you define like a strict set of keys that are eligible for this airdrop it can be say like people who owned a certain nft at a certain Block in which case there's a finite number of addresses that can claim that or it can be so anything you could prove in the ethereum storage Market potential try or it could be like just a list of addresses in a Merkel tree like a standard airdrop is done so the idea is that even the the reason that nullifiers uses it would only suffice for this claiming step because once you've claimed the nullifier to an account and you've claimed this nft or airdrop or whatever to this account that account can do whatever it wants with that information now it's it's come from a completely anonymous source and so it can it can go wherever and it'll continue to maintain that anonymity so the you can continue to transact that nft or your C20 but you just wouldn't be interacting with the original airdrop contract ever again so you wouldn't need another fire in the future yeah okay good so this is probably a silly question when people redeem it right they have to provide some gas so the guests must be coming from some account so even even though we have all these anonymity is uh probably hide the the edges that's going to receiving it but when people provide the gas this transaction actually links the account that's receiving nnp versus the account having the gas so it's still revealing like some information yeah that's a great question the question was basically how do you pay for the gas without the anonymizing yourself and there's kind of two main ways to do this one is uh the airdrop contract itself will pay for the gas the way this would work is when you claim uh the airdrop contract would record the amount of gas being used in the transaction there would be a certain Bank inside the contract to pay for that gas plus a little bit extra and so the idea is that you could send your claim transaction on chain uh or uh to a private mempool an Mev Searcher would actually be incentivized to claim this transaction act as your relayer in a decentralized manner because they're getting compensated for it uh because it contract is calculating and reimbursing them more than they would have paid for the gas that's one way to do it second way to do it with something like account abstraction where you can again have a third party pay for the gas usually out of the contract this can happen with say the contract doing an atomic swap with say the token that it's giving you and each to pay for the gas um similarly reimbursing the the front running relayer effectively um or you could send it to like uh uh something like keeper Network which would incentivize which is basically a place where Mev Searchers can post or people can post maybe ideas and maybe Searchers can take them you could use a mempool or you could use a kind of a private centralized or decentralized method to do that yeah that's a good transaction that's a great question though thank you so much bigger Plus