PSE Research Update: Web2 Nullifiers Using vOPRF

Transcript

Yeah. So today I want to talk about the project I have been working on uh from after devcon. It's called web2 ID nullifiers using VPRF. So basically what is this project about? Uh so shortly said uh it's about VPRF's usage to enable sudonmous systems for web two ids. So to remind you sudonmous system is a privacy preserving system where users action are linked to unique identifiers. Uh we can call it pseudonyms as well but not their actual identities. Uh example of such protocols such systems are for example semaphore rln plume etc. So basically all of the protocols that has this kind of uh what

we call nullifier is actually synonymous system. Um but there is a problem because there is no way to generate uh nullifiers for or from public data and actually web web two ID is actually uh public data. Uh so if uh if you if you remember the semaphore for example we register uh we have this like separate registration phase where we basically generate some random identity key and nullifier for ourselves. Uh we commit to it and then we reveal this nullifier.

uh we can do similar but actually this uh but actually uh we want to use this kind of uh like protocol uh for example for uh like in apps where we need synonymous systems actually and where we need these three properties uh it's like uh these properties are anonymity uniqueness and eligibility so basically if I bring an example uh let's say we want to build a voting app uh where all of the pc.dev mail holders will be able to vote for example. Uh the thing is that uh it's not possible to do it right away

to achie uh basically it's not possible to achieve these three properties simultaneously. So basically we can for example achieve anonymity and uniqueness. Uh that's actually what we have with semaphore. But with semaphore there is no straightforward way. there is no direct way to to prove that we are eligible for voting uh in this kind of voting and we can also for example achieve anonymity and eligibility uh for example to to prove that we are holder of PSC.dev dev mail. We can just do zk mail proof and we can output a commitment to our user ID and hash it with some random salt but nothing

prevents us from uh from generating new random salt. That's why it's not it won't be possible to track if we really voted only once. So basically it's actually it's called great trilmma pro problem uh described by Raro team. So basically what we can do is we can try to get closer to the ideal but there is no uh as I said it's not possible to achieve three properties simultaneously maybe unless we have uh IO uh so also I wanted to say uh if you have any questions please free to interrupt uh and ask because I'm not reading the

chat. So what is uh VOPRF? Uh VIP RFS are uh it's also like uh it's basically verifiable oblivious pseudo random functions uh are protocols that allow a client to generate deterministic random based on their input while keeping it private and at the same time having a verifiable output uh by providing cryptographic proof. So basically we have an output from this OPRF. We have uh we have a random number uh and we can say that and we can verify that it it was really indeed generated by this uh party uh and with this inputs it can be created using MPC uh so the

simplest uh using for example app specific MPC and that's what we're going to have in uh this protocol uh it's generally it can also be constructed with cost marks for example Uh so the idea is it's possible to use a VPRF to generate uh nullifiers based on the public input. Uh because as I said we can keep it private. So it's basically possible to put for example web to id send it to vprf and it will generate this random number based on that for us and it can serve as a nullifier. This is the just like uh high level idea.

So now I want to explain uh how it works generally. Uh does anyone have questions for now? Okay, I can continue then. So um I said that I I put here that we have two parties generally. uh so first one is user user with web to ID uh for which it's possible to create ZK mail proofs and also uh in this uh presentation I I I talk about ZK mail uh I put ZK maill in the in the protocol as an example but generally we can also use it with uh any other protocols as well with uh TLS

notary uh like ZikT with open passport uh and etc and OPRF and we're going to use MPC for OPRF. Uh for simplicity for now I can I I will just uh describe it as a like whole party. Uh but later I will describe how we can bring uh and add uh multiple nodes here as well. uh and it will have uh its own elliptic curve key pair. Uh we use for example baby job job curve or snark friendliness uh and of course public key have to be stored in some public registry. So it's like like a commitment. So we'll have

this key pair for example s and s multiplied by h gener some random generator. Uh so s is a private key and this is a public key. Uh so how it works uh I described two steps here. Basically what we uh what we could do we we actually could uh have these two steps uh we can we we could put these two steps into one step but that actually would require for us to change a lot of the code in the ZKML circuit. But uh if we separate it into two steps, we can just for example output the commitment. So basically we

can just add additional constraint to the ZK maill circuit and uh we won't change the code generally. Uh so basically we will just need to for example output a commitment from the KML circuit. Uh basically we just mix it with some random salt and I called it commitment one here. uh generally I call it proof. So basically it's a ZKML proof uh with commitment to user id. Uh so yeah user provides this generates this out proof and then also there is a new circuit uh which actually contains the logic uh ne like needed for the protocol and in this new

circuit we we do this uh commitment consistency check that's the first constraint. We basically check that we we we basically put this commitment as a public input and we check that yeah we indeed know the user ID and salt. And next step what we what what what we are doing here is that we are calculating has to curve from our user ID. I called it G. And now generally uh we would need to send this hash to curve uh this this point G to OPRF. But the thing is if we send it in a plain text it will be possible generally possible to uh revert

this uh because user ID like the set of all uh user ids uh is not that big actually. For example, if we if we for example calculate the if we have user ID and user ID here is just all of the males of like PSC.dev for example. Uh and I don't think it's a big number. We can just calculate hash to curve from all of them and we'll be able to reconstruct to get that G. So it's basically possible to do a dictionary attack. That's why we need to add some blinding factor to that as well. And for that we will just generate random number uh r and multiply g by it. I called it

commitment two. So basically commitment two is a elliptic curve point as well. Uh anyone has any questions. Okay I'll continue. Uh so now we send this ALF proof and uh this stuff basically commitment one commu uh commitment two especially to the OPRF and OPRF replies with uh OPRF response uh opf response is basically S and S as you remember is a private key of the OPRF node and we multiply it by commitment to and uh it's basically S multiplied by R multiplied by G And for verifiability property uh opf node also

needs to attach a discrete logarithm equality proof as also I can call it uh we can call it chumperson proof for site multiplication. Uh basically we check that we check the equality of this basically uh of these pairs. Uh yeah and yeah for the last step user gets this response. Uh and on the last step user can basically verifies uh user basically verifies all the previous steps including uh discrete logarithm equality proof uh that came from OPRF node and it also outputs the nullifier and nullifier is basically

OPRF response uh divided by R and uh yeah of we can do division here because division is basically multiplication by by an inverse And uh that's actually gives us this s multiplied by g uh or s multiplied by hash to curve from user ID. Uh so by doing that we didn't uh like we didn't learn anything about uh about this s and also opf node didn't learn anything about our plane has to curve from user ID. Uh yeah, so we also can update the protocol uh by using domain separator

app ID to have different nullifiers across different apps because right now if we just go through this process for example we have our web two ID for example our Gmail we generate nullifier for us for ourselves uh but then if we're going to reuse this web 2 ID across different apps we're going to have the same nullifier so it's it will be easier to track us, to track our actions. Uh, and we can just add domain separator, app ID, hash it, and we're going to have different modifiers across different apps. That's also useful here. Uh, any questions for now?

Alex has a question. Uh, okay. Um, Alex, can you just Oh, yeah. Yeah, I can. Uh so how do we trust the user to divide exactly by R? Is there a proof? Uh yeah so basically this discrete logarithm equality proof verification contains R if you remember because we have this commitment too and if user will use will input different R uh discrete logarithmic basically sheds improve verification uh will not work basically. So we also as I said we in the in on the last step we verify all of the previous steps all of

the like consistency in the in the protocol. So we basically uh recalculate all of the stuff that we had before and we also recalculate the commitment to as well. Um hold on hold on I think it is because uh the user want to obtain the nullifier which is s time the hash to curve of the user ID. So if the user doesn't divide exactly R, it will get like S prime times hash to the curve user ID and that the S prime is the key of another OPDF provider which is not the one that that uh maybe some system will accept. No, it's I think the Alex questions was more about can we generate is is the system sound generally can we

generate different nullifiers by just generating new R every time but generally no because even if we uh even if we like if if we let's say generate a R value on this second step uh and then we let's say we use different R on the fourth step the verification of this John Peterson proof will not work simply. But if we for example uh go through this uh opf process again and on the second step we generate new r and uh new r that actually that actually won't affect the result because the result doesn't contain the r at all. It all it contains

is basically s multiplied by hash to curve from user. Uh does it answer the question? So what what what is your question, Alex? Yeah, I think that the Sean Federson proof answers my question. I see. I see. Yeah. Yeah. So basically, yeah, as I said like we have this commitment too and we basically check again we we we try to recalculate all of the stuff on this fourth step. Uh we recalculate this commitment to again. So basically if we have different commitment tool it won't be possible to verify this. Uh yeah but is do I get it right that only the

user should know the random R. Uh yes yes. Uh I'm not sure that if Yeah. I think I think yeah it's a private input. It's a private input. Uh so yeah but you can you can notice here if we have only one node uh that will be the result right so s multiplied by h has to curve uh of user ID basically if you have only one node uh opf node let's say it has access to this nullifier because it's public it can

basically multiply this value it can basically multiply the nullifier by inverse of s and it will just get hash to curve of user ID uh and it will be possible to create to do a dictionary attack as well. So that's why we need to add more nodes. Uh so basically how can we do that? Uh we can we have like actually like few options for that. Uh I think there is even there are even more options but I listed a few. So first two probably uh simplest. So first one is just we can we can have n of nc. Uh so how to do that is basically we

instead of having only one node we'll have multiple nodes and basically every node replies to a user individually and uh so user will do this whole process with uh each node basically let's say if you have three nodes it will it will do it with three nodes. Uh and in the final ZK proof user verifies all of the individual uh Sean Peterson proofs and then it calculates the lineer combinations of all the responses uh and yeah of all the responses and basically similar uh like we can have m of npc as well. It will be similar to n of n but it only requires m responses.

So instead of verifying n responses, we can only just verify m responses and calculate linear combinations of n m responses. Like other option num suggested here actually is that we can have m of n m of n scheme similar to two as well but actually it's a bit interactive. So nodes will just coordinate between themselves and they can calculate one common OPRF response and one common shamp proof. So this is actually more laconic even because we can just verify uh only like one uh shamp proof and like and we we'll have only one opf resp response uh in in the

circuit in the final circuit but that actually like uh for now we we stick to second option because it's easier to implement basically and we can we can also do the same with BLS but that actually uh would add some like requirements to the pairing verification in the circuit and so we're not doing that as well. So yeah uh basically by adding MPC uh this final result will will depend like uh so multiple nodes basically will affect this result and not only one node. So it will be possible for nodes to

reconstruct to get your hash to curve from your user ID by with only like in case of collusion basically. Yeah. But yeah uh any questions to that point? Can you go back to uh two slides before this slide? The first one. Yeah. Uh-huh. So, so basically here even if the user uh like next time create another commitment one with another song the the end the end uh the like the final result uh the nullifier will still be uh like not containing this salt

right? Yeah. Yeah. Yeah. Nullifier only depends on your like uh on on your user ID basically. Uh so you cannot create a new nonifier with a new salt at all. Yeah. No, wait. They can't. Um, yep. I I think I can go uh further, right? So, yeah. Uh, now we have this uh like the protocol I I described it already. It's like not that like actually uh like difficult to understand. I think uh it's already useful uh and we are actually like

working on on on the implementation of it right now. Uh what we can do what else we can do on that what's what else we can build like useful with this is that we can create uh one global registry uh like I also call it global semaphore for web two ids. Basically what we can do is that we'll have one global registry app uh and we'll fix we'll set app id equals to zero and uh it will contain a merkel tree. So generally uh it will be a smart contract. Uh so basically in this uh

miracle tree uh we'll put uh yeah maybe so we have this pseudonym uh I will just rename like before I called it a nullifier here uh but we can say uh for for better understanding basically we can say that we can call it pseudonym uh and it will be hash of uh our this uh opf resp response. like sg and zero because we set app ID to zero and we'll store pop key uh that's equals to hash of pseudonym and commitment one in leaves uh so if you remember commitment one here is a hash

of user ID and salt so basically user has to store has to save the salt from the first step and who will store pop key in leaves So basically by doing that we'll uh we'll eliminate the need basically from uh for uh for going through through this whole process again and again for example uh let's say we have an web two ID our let's say like Gmail account and we want want to use it anonymously with nullifiers across different apps let's say like in some voting in airdrop in I don't know PSC forum like etc.

uh if we if we don't have this anonymous registry that would require us to go through this like opf process again and again but in this case with global registry we can only add our uh identity only once we can put it in Merkel tree and then we can reuse it. So basically basically what we're going to have is we're going to have this global Merkel tree root with all these like leaves with pop keys stored there and we also let's say we have some additional app uh some some app that is using this and this app has its own app root as well.

So basically to do an action we'll provide ZK proof of membership in an apps Merkel tree as well as in the global Merkel tree and verifying consistency across two. So we'll calculate nullifier by just as I described before. So nothing new here. Uh but that actually as I said will eliminate the need from uh going to go this to go through this whole process again and again. So with with uh with checking just like two membership proofs and verifying consistency there we we won't need to even generate uh newsml proof for example we won't need to go

through opfc we'll just have nullifiers uh yeah and we can say that here in this protocol the pair uh SG and salt will be an action key and uh SG itself itself will be like a viewing key because anyone that who will have this pair SG and sold will be able to generate proofs in this system and uh do an actions for us and SG is just like a viewing key. So anyone who have SG will be able to track uh our actions across different apps. uh not revealing like uh who exactly we are but just revealing our like identity

generally like revealing our like pseudonym across different systems. Yeah. Um anyone uh has the questions about this? Uh should I go forward? Um yeah actually uh if the nullifier is only the hash of SG and app ID then you can only use the nullifier once right.

uh that depends on the app generally because if the app doesn't prevent from using uh no what I mean is that uh people can just uh link the use usage of you in the same app using uh this notifier um can I don't fully understand the question sorry you mean like if we if we used uh the app once with with our so so so you so you so so you use this by revealing the nonifier right and do something yeah yeah yeah yeah so yeah we we basically do this like two proofs as I said like it will be generally like one proof uh right but then uh it means

that let's say that for the first time you use a nullifier that is like the action key to do something and then again you use the same nullifier to do something then people can link that two actions if you are in the same application If you are in the same application. Yes. Yeah. Then maybe we can like include something like session ID or Yeah. Yeah. Yeah. Yeah. That actually like was the suggestion. Uh we had this I I I decided not to include like too many information into this presentation because we like I already like put too much I think. Uh yeah. But okay generally yes that like was a suggestion from from from uh some I don't remember

his name from polygon ID I think team from pa ID team they also suggested similar thing that we can add session ID here as well like an epoch kind of yeah so generally yes and uh this is actually like was like like my personal idea and also Le's idea Uh but actually I found out found out that RARO team is actually working on something similar not specifically with all this all of this stuff with nullifiers for web two identities with webf but generally they also uh in uh EIP7812

uh they building this uh global registry uh where people can just put like different like put different information. So for example, if we will develop this, we can actually go for example with uh their specification and yeah just reuse their stuff. U yeah is the reason why is the reason why you have salt in uh for an action key but not for the viewing key is also because you don't want to connect two different actions in the same app or something.

No, I I like uh I I just said that this is an action key because having SG and having sold uh you will be able to do an actions for this like so sold is the hash of the user ID. Yes, sorry. S is used together with the user ID in commitment one. So you want to find you want to avoid dictionary attack on user ID. So you have to add salt. Yeah, I see it.

Yeah. Yeah, it's it's actually like a secret. It's a priv private uh private input. Um yeah. Um anyone has more questions? Okay. I think uh I can also describe Rarim Mo's approach uh to like similar stuff. Uh so basically Rarimo is a company that they build different things uh but one of the like like famous thing they built is a freedom tool freedom app uh it's a voting app uh for passports. So we have the similar problem with passports as

well because passport data like we can verify them uh we can verify the biometric uh we can verify the public key like the we can verify the signature provided by chip in the passport but we have the same problem uh it's not possible to generate nullifiers for this data for example if you have a voting it won't be possible to generate nullifiers right away uh so their approach is is that generally It's similar to semaphore with a separate registration phase. So the user uh users will hold a key pair uh just like basic like I don't know if like Ethereum for example key pair uh and they will add themselves into a

global miracle tree uh like this like 7812 as I described before uh by providing an off proof as well uh and off proof is actually similar uh to what I called off proof as well uh like the one that was on this uh first step here. uh old proof is in their case all proof is basically passport verification uh and also they commit to public data uh in in their case is it's basically hash of passport uh data group u and this actually like this this approach is trustless uh because it doesn't rely on

any other party or NPC as well but generally it lacks privacy uh because it's possible to do a dictionary attack and anonymize. So they don't add add like any random salt here. So it's basically like committing to a hash of password uh data. Uh what they rely on is a network privacy effect. So basically the more users registered in the system, the harder it will be to track who exactly performed the action. So it's similar to cashache. Um yeah.

So their solution I I I discussed it with them. Uh they said uh I asked why why like I I I told them that I mean it's not anonymous. uh they said that they're not uh aiming for now for large large scale deployments generally and um I mean they don't do for example they don't host like that important kind of like national votings uh and what they wanted to eliminate what they wanted to what what they didn't want to have is basically like another party they wanted just a trustless uh it's like selfish mechanism for

nullifiers. But actually like I had an idea and we also can think about this more is that we generally can combine uh like our approach and RARO's approach for global registry. So basically we'll do like the same stuff as RARO in their freedom tool. uh but instead of committing to a public data like instead of just publishing hash of password data we can uh publish uh like var response to this hash hash of password data. So basically by doing that we're going to we're going to have like kind of like the best from two uh two protocols. we're still going

to have uh like MPC uh security uh and in case of collusion if in case of uh var is broken we'll have uh privacy network effect uh that Rari Musim relies on. Yeah, that's actually it. Um anyone has have a question on that? Yep. Okay. And uh I also wanted to list a few uh open questions we have. I think generally we have more open questions

but the few I remembered is uh like first thing is probably uh VOPF network spam prevention. Uh so basically should it charge money for its services because if there is no spam prevention mechanism for web PRF network uh it will be just possible to to attack it with spam to like I don't to provide some I don't to to do some some kind of attack to provide like multiple like uh off proofs and just do uh the system. So there should be some mechanism for spam prevention. Maybe it's a it's a good to just add a fee or something or just burn Ethereum for

example uh when we use like every time we use we have a PRF uh like another question is MPC threshold parameters it's generally how secure we want we want our MPC and that actually depends on next question is should we like generally target large scale deployments uh for example big national load putings. So big like some kind of like like very important apps where the like where where the anonymization of users might be critical uh might be like really bad or we are just good from with going like for some small scale deployments for example for

kind of like organizational small votings uh like airdrops uh so basically where the attack uh price will more than like the result incentives basically the profits profit incentives and yeah more use cases and applications uh if you have ideas for uh for this protocol basically feel free to like I I'll be eager to discuss yeah that's it thank you.

Thank you, Russell. Uh, anyone have have has a question? We also have a discord uh I mean you know it probably we have this uh OPRF discord channel in the research section and we have on Wednesday 11:00 a.m.

C weekly meeting if anyone is interested in that can join. Yeah. Okay. Uh if nobody has a questions, I think we are good to finish this, right? Yep. Cool. Thank you. Yeah. Thank you a lot for coming, guys. Yeah. Bye. Bye. Thank you. Bye. Thank you. So, bye. Bye. Bye.