ZK10: ZK for authentication: How to SNARK sign-in w/ Google, Apple & Facebook - Kostas Kryptos

Transcript

[Music] um it's my great pleasure to introduce Costas chare or also known as Costas crypto and Costas will talk about ZK for authentication today take it away yeah thanks Philip so very quickly this is um work that we're we're doing for M labs and the Su blockchain however I'm working on this topic since I started on blockchain like uh seven eight years ago uh with one of the first developers of Satoshi actually Mye k then we couldn't find a solution uh on the first company that I was like R3 for Corda not at Facebook as well I used to Le the Libra

protocol for uh well we never launched there and now eventually I managed to launch a blockchain which is like shuie and however whatever you will see here is typically applicable to any blockchain in practice and some of the technology can actually be reusable um so I literally asked SBT today to give me like a an answer on on the uh question why most of the people apart from the Dig cannot join the blockchain world and you see the first two answers were related to ux in practice too many jargon like Words um cryptography zero knowledge proofs NPC threshold wallets uh secret sharing and all of this stuff and then the second

one is obviously the experience when you're getting into a wallet you're pretty much receiving something like that and as you can imagine the average Instagram user I'm coming from Facebook so I know how demographics work it's very difficult to remember all of these things and the other problem is um it's not like a regular password maybe people can remember sort passwords but here for cryptography we need something more uh with more entropy I I did some uh actually survey some people don't even know the words I mean if they are not native speakers uh some some of the words like I don't know um saddle stumble garment and and some others they don't know what they what it

means and in practice when they have to use it it's unfamiliar to them and there are many situations where the words are very similar imagine the three yellow things there and it's also another thing that it's uh like orthography people don't know how to write them down and in practice we wanted to solve all of these problems and we said okay today metamask and all of the uh like uh most popular world are going into this direction of requiring the pneumonics can we do something else and actually the the whole question here is can we not change the way people are authenticating either in a website for web 2 or now in the blockchain they don't even know that they have a blockchain account and this is exactly I mean typically you might say oh this might be difficult how do you connect

Google and Facebook and all of the other companies with like blockchain because if you don't have a key then oh it's Google custodian and then you will see how together uh we're going to unfold all the situation and how zero knowledge proofs can help here that eventually you don't even require to remember any passwords any keiss nothing and still Google not to be a custodian um so accessibility I mentioned here and you will probably have seen uh a product that was advertised recently in the news like ZK login and everyone is saying oh if you manage to solve this problem you're actually solving the onboarding problem but onboarding is not uh like the full story in practice for the first time you

might even have discoverable addresses the same thing as PayPal and venmo and sometimes even revolute I type my email and I know how to send money to someone and this will change obviously um uh the the world of people who are not familiar with like all of these uh hexadecimal addresses and the QR codes for actually sending money to a very long string and if we can manage to solve this together like killing two birds with one St Stone uh where they sign in with Google then it will be like awesome and great um so in practice we got whatever people are used to we added extra privacy because this is required and with your user ID you're creating an account on sayain

this is enough you will be surprised now because you say Okay user ID Google knows my user id can user can Google or Facebook actually impersonate me and you will see that with the magic of zero knowledge proofs and a few tricks they cannot um now let's go to the architecture there will be some math here but I will try to keep it simple um but in practice if you understand the whole logic behind it how we combined all of two open ID providers with zero knowledge proofs eventually you can implement it either on like sui or you can even uh think about applications elsewhere so what it's happening when you're signing in with Google in

practice in the background You Don't See but you're receiving these things this is a Json format like a response from Google that successfully you you are a user the the username is actually the the flag with sub the field called sub I have uh striked out some of the elements there because it's one of our subs and someone don't want to be uh anony sorry non anonymized uh but Google is signing with some key that it's in the top all of these things that it's in the bottom and in practice you can add more information here for example if you go to Facebook you will probably see your photo you will probably see your avatar uh you might see also your full name your email if you want and everything so Google

gets all of this information from the um uh permissions that you requested it creates this Json uh structure we call it JWT and it signs it with a key that is in the jwk like the top one like there is an identifier for the key um as you can imagine with this we cannot go to the blockchain right there there is nothing that can help you to sign transactions so even if we had a way to to use like the the signature that we get from Google to go to the blockchain it's not it's not easily um uh like understandable how you can do it and there we added many tricks that I don't know why nobody tried them in the past but we had someone who participated in the ceremony we had very recently in go

16 it's one of the most popular cryptographers in the world actually how the heck we didn't think about it uh all of these years and I guess it's because zero knowledge proofs were not at the stage where they are now like regarding uh the efficiency and the second one there is a very special trick here that without this you couldn't do it which is unrelated to ZK but we use it very efficiently so the first trick before we go to snarks we realize that some providers are having this value in their JWT there is a nons here and the nons is typically provided by the user to avoid replay attacks I don't want to get the same J JWT again and again and uh in practice Google is

asking you like when you're doing login with Google the ux like the browser is sending a random value to the request and this random value goes there to the nons and then we said oh if we can have the user actually injecting something into the JWT can we have the wallet creating a public key fresh public key random public key and put the public key inside the JWT and that's the first the first trick because the public key is also random in practice you are replicating canons if the public key is always different you have a new random value and there you can also add more things it's not only the publicy you can even add personal custom expiration you can even add rules any in any case knows is is like

metadata that the user wallet can actually provide to something that Google will sign and then eventually what do we have from Google we have a digital certificate over anything that we requested from them to do but the digital certificate it's not only the data that we put inside because everyone can put like some random value it's linking this because this is a structure signed by Google with your username with your email and now we manage to get a certificate over our personal identifier along with a public key that we defined and now oh there is a public key now maybe maybe we can use it for a blockchain transaction and let's see so the second trick is how do you use this let's

assume that you manage to put a public key there how do you use this for for blockchains you have to Define some address type where the long-term publicy is not there anymore because there is no long-term publicy and typically if you go to the Bitcoin it's typically your h of your public key but now there is no long-term public key we had to find a way to put the identity now as part of the address derivation and then let's see how we're going to use the ephemeral key that we injected inside JWT and here we start with some solution that didn't work for example strowman uh solution would be let's have a h your address being the H of the provider like Google your wallet ID let's assume metamask and the user ID which is like Costas and ml.com and this however uh might have some

issues because someone there is nothing randomizing my address there right and I have a privacy issue everyone can see my user ID just by enlisting all of the providers all of the wallet IDs and all of the emails and someone can figure out oh I'm losing my anonymity now someone can figure out that my address is uh this particular on bitcoin on sui or ethereum or wherever so we have to think of something else and then we said okay let's add some random randomizer here and we added the salt and someone says okay the salt now is protecting you against uh uh someone identifying your address uh and Ling it with your real identity but there is a question right who is skipping the salt because we said no

passwords previously you cannot have the user having the Sal and the solution is uh although we say uh this is not safe and I will explain why let's use the wallet because the wallet cannot impersonate you the wallet cannot sign on behalf of you on Google because it needs the credentials of you but it's fine to keep the salt because just with the salt it doesn't make it a custodian it's just an extra value and every time you go to your wallet it will provide you the salt and then with this salt plus your Google you can go and create a transaction on uh the blockchain the actual solution however is this one and this act helps us to even hide uh more things from the JWT and we're doing a bit more complicated um uh derivation

of the address and here we're using zero knowledge Pro friendly hes so in Su at the moment for ZK Lin we're using this type of addressing so it's the provider id Google then we have a ZK of the wallet ID the user ID and again another ZK of the and you will see later on why this is super useful because we're not solving only the onboarding problem here we will help on discoverability as well um so having this in mind you can already I mean people who are cryptographers or can even understand that the H is an One Way function how someone now by seeing a address on chain they cannot identify my identity because there's some Randomness here and at the

same time they cannot even see my wallet because there is a h and anything inside the K has is not sent uh publicly that we hide it with uh with zero knowledge uh just for your uh understanding the JWT format defines AUD which is in practice for as a wallet and the sub is the uh user ID of the user and we can also have email someone using the email as identifier and you can pick whatever you want here we don't specifically say that the sub is the identified someone will use there might be social applications for example I don't know Zinga pocket and others that they will say oh I want to identify a user with privacy but now with their Facebook [Music] account and now we're going to the fifth

trick now that we have a zero knowledge proof address we can get the JWT as a private input to the zero knowledge proof uh um uh circuit and we say okay let's create a zkp that verifies the correctness of the JWT itself that it has all of the fields that you want it also verifies the open ID providers publicy and signature in practice because we said that this is signed by Google but when we talked to all of these open ID providers they said okay even myself I don't want to track people on chain so because I know what signature I put on the JWT and I know the JWT please hide the JWT from the chain and also hide my signature on chain and then we put the signature

inside the verification function of the circuit and we verify RSA inside the um the zero knowledge proof and then the other thing that we check is oh there will be a fresh public key this fresh public key every single time will be different let's also verify that the public key that we sign transactions with is inside the nons of the JWT and finally that I know the sold right I know the pimage of the address because this is very important every single time I'm going to take over the address and be able to sign I need the zero knowledge proof that I know everything inside the address and all of these are actually defining uh the system that uh like the um ZK login is using all of the ZK for

authentication and as you can see it's like a combination of tricks you couldn't do this without having a particular address uh style you couldn't do it without hiding everything from the JWT and you couldn't do it even with the requests that sometimes are very strict from the open ID providers that I don't want to track my users because I might have an administrator who is Rogue administrator and they can do uh some identification attacks so we put all of this into um like one slide and how it works typically you are getting the JWT by signing in with Google you are putting an ephemeral public key inside the JWT Google returns this back you're adding ass salt and the ephemeral key you sign the transaction and now the verifiers

compared to previously on the blockchains that they only do signature verification now it's an ephemeral signature verification you have to convince the validators that you also have a proof that you you were the owner of this address so as you can imagine like verification now requires an extra zkp but there is a benefit here this can be parallelized every user and this is stateless I'm just going into I don't know Bitcoin or shuie and then I say okay I'm signing something and this signature verification and the proof can be verified on Parallel without requiring anything from the state it's just a verification against some address right you don't need to know the balance of the address or the object that this address on So in theory you can have

validators that can verify all of these things in parallel and that's why fast zero knowledge proofs and parallelization make this possible today that it wasn't 3 four years ago um so the whole story is I don't know if like the the font is uh big enough but you take an open ID login you're adding zero knowledge you're generating an address now linked to the identity there is no public key internally and then uh just by this you can view and manage assets I have an example on how it works in practice um but yeah that's that's the full flow the user is like the app front like the user below the app front end is the wallet but as

you can see the user doesn't see anything happening just looking with Google Now okay we said there is a JWT format but is everyone supporting it that was like a big exercise and we went to everyone like Facebook Apple Google Microsoft do you support nones because not everyone is supporting nonis and then we had we said okay let's take one by one try to get the JWT use the ZK Lin algorithm and see if we can actually embed inject a public key internally because this one will make it compatible and we realize that at least the top five uh Google Facebook twitch slack and apple are compatible with this approach

for the others are still reviewing the situation and if the nons is not there we're probably going to discuss with them if you want like your identities to go on chain imagine your Xbox and your Microsoft and you want to use this system please uh do according to the specifications of the K login because in practice this can also be used outside the blockchain we don't know how this technology because it's a primitive and I will explain later why it's super useful we don't know exactly how this will be used in in practice because it's not tied to a particular wallet every everyone can go and implement this now it's not like it's it's a metamask uh uh like IP whoever wants to implement this it's open at Native uh like functionality not in a smart contract

and now you are a wallet provider you want to have zero knowledge proofs on your wallet advertise you have a wallet you can go and raise money you can do something better like faster provs faster verifiers um and you can have a business so now some cryptography stuff let's see how far are we okay I have five minutes I'm good um so many things here right how can you make this implementable in something that in one second you can have a proof you have to keep the circuit as small as possible and here we manag to say that 1 million constraints with some uh like good provs it can actually happen in one 1.5 seconds and this is okay this is

like pretty much what visa and master cards are doing when you are paying with with your credit card um there is another benefit that I will explain later at the S by by the way I can I can give you a hint at the session of your wallet you don't need to implement for every transaction zero knowledge proof because imagine you open your wallet you define the fresh public key you get this uh zero knowledge proof over this public Key by injecting the public key into the um like the cookie that Google is giving you and then you can reuse it you can sign many transactions with the same public key as long as you remember this public key you can use the same the same zero knowledge proof if you change it if you close a wallet and you go back again you have to again log in with Google get

a new zero knowledge proof and do it but most people especially if you're playing a game imagine you're playing chess and every every move goes on chain you're having your wallet open right so one zero knowledge proof and then you use it um but anyway even for the one we wanted to keep it like small and then uh the most operations are actually occupied by the SAT 256 the RSA signature verification and some other like posidon Hing b64 because unfortunately Google is signing the b64 format of the JWT not the B of the JWT and you had to stick with that for RSA you cannot just use the RSA verification you have to do some optimizations here we did a small trick

uh like inspired by the libraries that you see at the bottom instead of like Computing the r uh equals a * B uh mod mod P we use the one in the middle we actually uh do check an equation uh between two uh two particular values and this is actually faster um we have audits on this uh it's already used but without this optimizations it wouldn't be possible to happen in one one.5 seconds and then the same thing for B 64 B 64 is a it takes like 10% of our constraints this is what you have to pay unfortunately because uh this is what JWT is this is how the uh the standard works but we have to make some

optimizations here um and um in this in this situation we we have some uh like small downside that you can see at the bottom to make the Json parsing as fast as possible we are assuming that the JWT provider is having like correct uh open ID uh outputs like the jwt's and we're not handling in practice the The Nest uh values this is the only requirement that we have but we haven't found any open ID provid who is not conforming to the standards so this is this is typically okay um and the final one which was the most surprising one you have to do some lookups inside the JWT right you're getting something

and then you say oh find the user ID to check if it's a preimage of your address and find the wallet ID internally to check again the same thing you need slicing over strings you need something to pass the string and eventually take some values from there and then you're using these values to all of the constraint calculations and this is very important to do it properly because asymptotically you know that the the naive implementation would be n * m constraints because imagine I have to split the JWT and then eventually look in all of the uh uh elements if I find for example AUD that we said it's the wallet ID or I find my email which is my email and so on and then we realize we

can do something better and this is uh the one here like the third from the bottom that as you can see asymptotically it's not better than the n * m and this is where a difference between what MLS is doing and what Facebook was doing so in Facebook we had like a situation where most cryptographers are thinking about the future like even asymptotically bring something better to the community but in real situation we're talking about this a case of 1 million Gates and if you are using our uh optimization you can go from 160 con 60k constraints to 33k constraints so even if asymptotically this optimization doesn't make sense you

know in practice when you are having cryptographers in your team sometimes you have to think of the real parameters and if some algorithm can work here better even if the ASM totic complexity is the same and here it's a huge gain right because imagine we have to search for four five Fields there we said the whole um U number of gates is about million and we already if we didn't do like the optimized approach we would I mean just with five lookups we would cover like more than half of the of the constraint just using slicing constraints and now we manage with 33k to actually have this five without occupying all of the uh gates in the system that's why sometimes when we have generic VMS in my opinion it's good and probably you can go to the next level to

the next step we had bobin before uh like talking about miden VM on polygon and all of this stuff but there are situations where you have to handcraft your smart contract and actually the the circuit itself if you're doing generic VM instructions you might not be able for the particular problem you are solving to get the efficiency that you want and here we had to do handcraft circuits um now optimizations we did many more things right even on verification this is running on 100 plus validators what do you do here right you need the paing oper they want at the bottom to be run as fast as possible so you had to do some pre-computations and in this case we prepared the verifying

key it doesn't you don't uh need to know about this stuff but uh this is an optimization but because verification is stateless as we explained before you can do it on Parallel in practice many blockchains can have validators that are multi- server validators the signature even on bitcoin and ethereum even personally I don't see why it's happening on the same server you just verify a signature same thing as web to as Facebook and Google are public now and they can support so many users signature verification should happen on of of loaders the validators is receiving messages you're doing signature verification very quickly and then you move all of the messages to the uh to the actual core of the consensus because signatures are stateless and the

same thing now with zero knowledge proofs and this gives us the ability to use zero knowledge proofs in a in a situation where the server wants to parallelize and they can do unlimited users in practice the same think now now do you know Google and Facebook how they work right you have the database and before the database you have 100 of loaders it's I mean you receiv receiving all of the SSL uh connections they can do uh the the SSL decoding and after that no encryption anymore you can do this on the blockchain when you can deal with stateless information something that doesn't have to do with the transaction data itself and the state and signatures it's just you're giving an address a publicly and the signatures and you verify it without having a state so everything is paral I iable here and that's why we can we can manage to do

all of these tricks and plus the lru cast trick that I mentioned before is because as I said whenever you are sending a zero knowledge proof along with your transaction you don't need to verify this the proof again and again it's reusable if you didn't close your wallet and this is super useful to understand that even if you have like back chain uh backend provs like every wallet will use it once per day or once per hour or once per two hours it's not going to use it for every transaction it's doing which is super cool otherwise it would be super expensive and here is how it [Music] works in practice imagine logging in with Google very quickly you're going to uh to your account voila I have an account nothing else and then you can

send money transaction and as you can see there is no password anywhere in the process so in the background all of the things that we explained before happened and imagine what this means for the game industry especially uh when we don't want people to change the way they're authenticating and there are some big benefits here let me go the video is a bit tricky and the main benefits here are these things and as you will realize it's a native uh authenticator and chip but there are many cool stuff you can do especially in the middle

discoverable addresses now with your email because if you know who someone's email is you can just send them AA and then they can receive money automatically you can even have a zero salt for example if it's pay amazon.com they don't care about the Sal people just type pay amazon.com and they send a transaction directly they don't need to remember any addresses and it's also claimable you can send money to someone who doesn't have an account just go I send you some money just go sign in with Google and you will have access to the account which is super great right I mean this is doesn't exist now in the blockchain and the final thing is you can combine it with 2 fa like either login with Google or login with Facebook or login with Google and login with

pneumonic and also geofencing because now you can have zero knowledge proof hassis and this is the trick I told you before you can now do the the situation where with an extra zero knowledge proof you are proving that I'm someone with a do com domain or a doco UK domain Orit domain or VR domain and this change is completely how addresses like imagine gobling companies want to enforce some gensing all of this work that's all thanks a lot all right any questions I saw you had thanks hey uh so quick question just

to make sure I I got it cuz I did get a little bit lost um the uh cross session Persistence of um of the blockchain uh history of the history for for an address is achieved through the Z knowledge proofs or like how do you access let's say that I log out uh I carry out I log in carry out a transaction log out and then log back in and access that it's all based on how the address is generated as you can imagine the address is just a has of your identity if you can prove that you have a valid JWT with some publicy uh that goes to to whatever address someone is providing you are

good to access this address and with the Emeral public signing transactions and this is uh static right it's not Emeral address there is nothing here that is Emeral the salt as we said it's a static salt user ID obviously is atic is a static user ID wallet ID static and provider is Google right there is nothing that Chang your address so when the next time you go to to your wallet let's assume you were um offline for one day then you go to your wallet you say to your wallet okay wallet give me your salt your salt I will do a Google L and I will provide to the blockchain a zero knowledge proof that I'm the owner of this address and this is the key that you're expecting now for the next transactions to sign so the history is maintained because the address itself is

permanent if it wasn't permanent this wouldn't work okay so the entire system depends on the Integrity of the salt right that the salt is fixed yes so if that salt gets compromised your if it's compromised someone needs also to compromise the Google otherwise I mean just the salt is not enough to it's a two FAA by itself right you need this but you also need to log in with Google all right further questions I just have a naive question that how to verify that uh your loging your loging scheme is really zero

knowledge and Anonymous which means that if I try to if I try to log in uh to Google how to how to test that and from the outbound traffic outgoing traffic or incoming traffic and to to to to trace the packages packages all or other ways to to verify if you're okay so by the way the JWT we never send it the signature from Google we never send it because we typically send the zero knowledge proof and the fresh public key you can see that the zero knowledge proof and the fresh public key go to the same address as you can see with every other address on chain that this public

key is uh uh for a particular address but nobody's learning about this data right because you never send these things you don't even send JW itself I mean the Jon that I show you before it's a private input never goes online never goes on chain oh so in practice this is how you maintain your uh anonymity here oh so and as I can understand there must be a there must be a intermediate inmedia to to send the to to to verify the zero knowledge proof and no the zero knowledge proof is verified by the validators validators yes but the the the JW is a private input of the zero knowledge proof not a public input oh so only the user

provides this and then the validators verify it okay I I got so yeah I think we need to take the next questions on offline yes let's take the next offline I will is still around all day so please find him during the break and then uh yeah let's thank Costas [Applause] again