ZK proofs of JWTs by Justin Martin,- 3 23 2022

Transcript

okay uh how many people we got here nine there we go one more got ten I think that's what we were expecting I yeah I think okay I'm gonna hit record here and that works as well um let's see it wants me to sign into Dropbox I think that Charlie can record right okay yeah if you're recording then we're

good all right um so yeah intro here um or a little bit of background on what I'm talking about um so uh the way I got involved with the PSE team was um I was working on a little Pet Project after I I quit my former job to try to figure out zero knowledge stuff because I kind of saw the opportunity uh in this space and thought okay what what can I work on that is you know that connect that I can use to learn this space and kind of find the edges of the problems uh and also what

what can I work on that could actually have an impact because I have a hard time learning by just like fiddling with useless stuff I I like to go straight for something that's that's useful so I went straight for identity as a problem and the question of how do we in the crypto space make use of the existing identities that people have there's all sorts of solutions out there right now that are uh you know building new identity schemes and those are awesome but how do we use the ones that we already have and in that space there's you know mostly just centralized Solutions where

where you have a trusted Authority uh like um let's say like git coin for their grants matching thing they have all of these uh ways that you can verify the accounts that you have um and that in you know the more accounts that you can prove you have on various platforms or like proving that you have an account on a number of platforms you can improve your reputation there um so those are centralized where you're really trusting git coin to uh you know do the right thing and not say manufacture identities or or something like that you're also trusting them not

to disclose your identity information to anyone so they know who you are based on your accounts and and they could theoretically do something with that information so those are the sorts of problems I was looking to solve um how I approach that is this is using this notion of of Json web tokens um so what jwts are is um you have say like open ID authentication providers like Google and Twitter and Facebook and all of these social identity providers but open ID itself is very like server client and it's somewhat like uh synchronous so you

authenticate with them and they give you back like some some like essentially like a temporary API key to use but many providers are are starting to support Json web tokens which are um they are signed credentials or signed claims about your credentials that you can use to authenticate to services and in particular you can authenticate to external services that aren't hooked up to that provider's uh uh oauth uh service so the way they work is you go to the social identity

provider or whatever auth provider and you authenticate with them and they give you back a Json web token and I'll get into the structure of that uh as I go into kind of the nitty-gritty details but essentially it's a it's a blob of encoded Json with a signature on it and that signature is from the private key for the identity provider so you can take that token and you can go to another service and you can say hey here's my JWT you can see that this JWT is signed with the public key of the identity provider and it contains these

claims like this is the account so because I know this JWT you know that I own this account or I've somehow gotten somebody else's pwt but there's ways to to mitigate that um so I don't say like user ID this and then you can use that to authenticate operations um so that's that's the 30 000 foot view on what jwts are um jwts look like this and if that makes absolutely no sense it's uh understandable so it's a bunch of base64 encoded stuff because one of

the core characteristics of jwts is that they're highly portable you can take them around and uh you know send them to Services uh and you know you don't want to worry about encoding problems so they're all base64 are encoded uh the great thing about this tool on gwt.io is that they provide a decoding of DWTS so you can see got a header which says this is the hashing algorithm um this is the key ID from the identity provider and then here's the payload with like here's the issuer the the subject of the jwd so in this case this is from my Twitter account so it says

Twitter and then my Twitter account ID um and a few other fields here so that that's what jwts look like on the inside and so what I want to do is figure out how to create a zero knowledge proof of this because sending this thing to say like a smart contract to verify is both going to be pretty expensive um to do because like in the case of most jwts it's like RSA signed so you take like

this like the the header and the payload and then that gets signed and so that the signature the RSA signature of that blob is like longer and the blob of data itself so how do we uh get yeah how do we create a zero knowledge proof of that um you also don't want to like there there might be some fields for some providers so you don't want to disclose like Googles show your real name probably don't want to give that away on chain um so um

I'm going to narrowly focus in this case on off zero off zero is basically like an identity provider aggregator where instead of building support for every individual identity provider uh and there are various schemes and they might not even individually support jwts off xero basically Aggregates all of those into a single um endpoint and a single sign-in key now admittedly this does create a trust situation where you're trusting auth zero not to say Forge credentials

um so that's a caveat here but for for this purpose it it makes it a little simpler to to show and they support like 50 different identity providers so it covers a lot of the landscape um so yeah auth zero uh you create basically an application and they give you back some uh off sorry Olaf client credentials um and then you can use that in your application um so let's see here I'm gonna I'll quickly show

my very crude prototype application which is over here uh this is the the key data from off off zero uh but here's my very crude uh prototype application so um essentially this uh just like for each of the providers uh can go through the credential generation process um so let's say I'm gonna off to my Twitter and because I've already done it it's not actually gonna make me accepted but it would show like authorized application um and then yeah it gives me back uh JWT so down here this is the raw JWT it's

pretty long and ugly to look at right here but there it is and here's the breakdown of what it contains so it's got this key it's rs256 so it's an RSA signed um FHA 256 hashed token and here are the claims there's my Twitter account ID um yeah and here's the the big long long long long signature um and then uh so um the the masking uh I'll get into what I'm actually doing here but basically here's the the masked uh

token so I only want to disclose parts of it so I'm only basically showing a couple of chunks of it as public signals for my proof and these will be the ones and I'll show you what that actually breaks down too um so simple app or a pretty simple application um I'm not going to run this now so I don't pick my processor but uh if I were to click private privately claim it with the zero knowledge proof it'll run my circuit uh like it'll generate the witness for this create the proof and you can see some of the the proof data in my my console here might be a little hard to see at the moment but I'll I'll

show it in action shortly um so yeah I'm gonna get into uh what the circuits look like and kind of some of the the issues that I ran into as I figured this problem out um so here's my circuit if anyone who's worked with sircom knows that it can be a little tough to coherently describe what you're doing if you're doing something complicated in a zero knowledge circuit but here it is the important parts of this are basically

um generating an sha-256 hash of um of the the header and payload concatenated and then masking that out so we're only disclosing parts of it um so it's a pretty simple circuit at a high level uh it goes through run some sanity checks on like the parameters to the Circuit um one of the the things that I realized I needed to do in order to prove these uh jwts in a an efficient way in a solidity contract is

I needed to densely pack and then unpack my inputs and outputs so basically what I do in that respect is I take the The Blob and I break it up into um What I Call On the circuit here uh the the segments of um data which are 248 bit signals so I pack chunks of data into 248 bits and so instead of passing like individual bytes

in which would be a lot of signals I just pack uh pass in um like chunks and then within the circuit I take it and I expand it out into internal constraints I I take it and I convert it to a series of bits that I can then pass into the sha-256 circuit um and then yeah Ash that it comes out with a uh with basically a 256-bit signal technically smaller

because you can only get like 254 bits out of a signal insert column um and then I take that and I mask it and then I repack it into um you know dense signals that are going to be public the masking part is basically just coming into the circuit is a series or I'd say a a sequence of um true or false signal saying like uh this this segment of the uh of the payload will be output as a public

output and I can go into detail on that but I'm probably getting too deep into the logic here already um one of the big issues I ran into and spent a good couple of months working on was um circumlib does have an sih-256 circuit but it is fixed length and so it can only hash fixed length messages so you have to know exactly how long your message is going to be that you want to generate a hash for when you compile the circuit and that doesn't really work because

jwts can be variable length like depending upon the the length of the payload and the the header and depending on a number of things it could be you know a a wide variety of lengths so I needed to figure out how to make a variable length sha-256 circuit so I took what sir comment made or somebody contributed to circumlet might have even been majority and I um figured out that there's an interesting approach you can use for doing like

variable length operations which is and I the I've been calling it um so there's this component from I believe it's from Macy that they called like a qn selector and basically what it does is it takes a a sequence of inputs and then it can in the in in the case of what I'm doing here I pass it in um what I call the the T block so fdha 256 uh has 512-bit blocks so um when you pass a message in you can

tell the circuit like okay this block is the last one and then you can use the the t-block signal to say um uh you can say basically uh is this why uh one of the blocks uh less than or equal to the t-block and then you can uh basically for each block um for each block you say like is this one uh of the right ones and then you can like multiply it by that to either get a uh

either the block value or zero so but that might be a little bit of a complicated explanation but anyways um this gives the ability to Hash over arbitrary length messages up to some Maximum you have to say like what is the maximum length but you don't have to have a fixed length and then yeah it outputs uh um the hash at the Block that you specified um yeah so there's uh that was one of the big problems was figuring that out and it took me a good long while but um

it was uh taught me a lot of things about how to think about writing circuits um so that was a big part of the process um another big question was like okay I've got base 64 coming in here and um for called the logic correctly it's like uh four bytes of base64 equal three characters um and so I had to figure out how to like mask the um the payload in the outputs but with these weird like segments of data

um that were like four bytes in length um so there's there's a whole uh area of the logic that has to do with dealing with base64 um and I could go into that but uh that was an another one of the the big problems I ran into was dealing with weird um essentially like data parsing in a zero knowledge circuit um yeah so uh essentially in goes appealand and out comes a hash uh and a masked

uh masked version of the payload so we can take that and this is the part of this that just isn't done at this point um so there's because of how complex it can be to um like structure the data going into and out of this circuit and verifying it the way that this would be used might end up being like highly specific so if you're using it for like if one of the examples here uh for my like verifier contract is it