Privacy-Preserving Digital Identity with Abhi Shelat | a16z crypto Research Series

Transcript

All right. So, I'm uh excited to have Abby Shalad here today. Uh Abby is a professor at Nor Eastern and an engineer at Google and he's going to tell us about uh work he's done recently on zero knowledge credentials from ECDSA. Take it away. >> Thank you, Justin. And thank you Justin and Tim for inviting us here today uh to sort of talk about our work get feedback from you. Uh my colleague Matteo's also here in the audience and we're around to answer all sorts of deeper technical questions about this. Uh this talk is a very high level overview of what the problem is and how we've basically solved it and we'd love to get your feedback especially on techniques that can be used to optimize this approach even further. So, first I'm going to describe what the problem is. And in the

identity world, the version of Alice and Bob are basically Erica and Yan Mustman. And so, we'll we'll take Erica's uh situation here. This is Erica's credential, and it it has it's a physical card that she's given to she's given by the government. And it has a bunch of privacy issues that we'll talk about, but also Erica's very tired of carrying around this extra card. and she's also tired of the following phenomena which happens if she needs to prove something about herself on the internet uh like any sort of KYC or any sort of age. Typically what happens today she's asked to take a photo of this card and upload that and as a privacy person you might think that this is terrible because out there are several databases maybe partially

unsecured and whatnot uh that essentially hold uh images of thousands or millions of people's driver's license. That's probably not a great thing. uh for uh for the world to have. So the task is digitizing this digital identity. Okay. And so that's thus the notion of a digital credential and essentially this cartoon sums it up. There's some government that uh you know has some sort of high security process and it issues a digital document that's signed by essentially that uh government server and it's issued to a user's device. And all of these things have very specific meaning. Uh the data that's on there is essentially private to the user. So uh in all of the wallets Apple and Google and so forth, they're they're architected in a way such that

the information is private to essentially the issuer, the government and the device, the intermediate parties essentially should not in principle and do not uh learn any of the information. That's the digital credential. And what can Erica do with her digital credential? So in fact actually before I do that, let me say that this type of technique is actually a real world protocol today. It's deployed in many US states like this. It's deployed in several countries uh like Australia and Japan and South Korea and India have certain versions of this and the EU is basically adopting a mechanism like this in this EUD wallet project European Union digital identity wallet project.

Uh it's a longstanding uh collaboration among the 27 states and even this year they have something called the age assurance type of mini wallet they call it. Uh all to kind of solve the problems that Erica has. A, she doesn't like carrying around the plastic. And B, uh, when online situations and even in person situations, she needs to essentially disclose certain attributes about herself without revealing all of her attributes. So that's essentially the privacy problem. And we're going to talk about what you can do with the digital credential. There are two use cases. There's an in-person use case and there's also an online use case. And uh, all of these topics apply to both of these, but today we're just going to focus on the online portion of it. And these protocols are kind of uh before we got involved in this space uh there had

been a lot of work on identity at least uh at least two or three decades that I remember uh from Microsoft working on this stuff uh in in the in the n late 90s. Um today there's this MDOC standard and this like selective disclosure uh JSON web token uh standard as well SD jot and an important privacy feature that has been designed in these legacy protocols is this notion of selective disclosure. You can disclose, for example, that your age is over 18 without disclosing your birthday or like for example disclosing your address or your gender, whether you're an organ donor, all the other things that would be included in a picture of your ID.

Okay, so the problems we're talking about digital identity and how to present a digital credential. Okay. And I told you that there are these legacy protocols that have already deployed. And one of our constraints is how can we improve the protocols that have already been deployed and all of the infrastructure that is currently used for these type of things. Sort of more of an engineering concern. If we could design this entire system from scratch, including the cell phones, and we can optimize all of it for working with digital credentials, we might have made other choices. But that wasn't the world that we were kind of in. We're kind of applying the best of our essentially zer knowledge techniques and and privacy techniques to what currently exists. So this is essentially a cartoon of what these current legacy protocols do. So uh

essentially right here there's a user that's like Erica and her device. There's a relying party RP or website let's say in the online case. And let's say the website wants to know that Erica is over 18. So technically the protocol that's in that's defined today is of this form. the relying party makes a request that's for the attribute that uh that it wants as well as some sort of nons uh as well as some other encryption parameters. This entire protocol is encrypted end to end. Uh but importantly they want to make sure that you don't just replay a previous transcript and so you have this freshness with the knots and the response today is essentially composes of three parts. This m document I'm going to show you what that is in a second. a pre-image for the attribute that you want to disclose as well as a

signature on this nons to essentially prove livveness and in the status quo essentially the statement proved is the state of Massachusetts has produced a signature on some document that's on my cell phone that includes this attribute that's kind of at a high level what we're trying to prove and these five steps which we'll dig into later are essentially what the relying party currently does to verify that this claim is true and of course foreshadowing what we're going to do is replace this check that would have been done on the relying party side. We're going to replace this with a zero knowledge proof that asserts all of these particular checks and we're going to run the proof on the user.

Okay. Uh so essentially the verification check is uh you know done on the user's device and the output of that is a proof that all of those checks pass and this relying party then just verifies the proof. That's kind of the high level architecture. Now let's get into some details about how this particular protocol works. Again, one of the constraints is we'd like to build on top of what is currently deployed and basically make it a no-brainer to deploy the SER knowledge. Um, and we can talk about some of those uh, you know, issues a little bit later. This is what a sample M do this document that is currently used for this type of protocols. This is what it looks like.

It's essentially an encoded form of this object. And this this object is essentially signed by the issuer. This is the document that is essentially stored on your phone along with its signature. And I'm going to point out a few important uh part parts of it. First of all, this green part right here is essentially how the people who designed this protocol who weren't cryptographers, how they implemented this notion of selective disclosure. Their idea is this salted hash. What they will do is take all of the attributes that they want to that that that they want to associate with the individual and they want to sort of hash those and include hashes of those into this document that's signed. Uh it also has this yellow part which I'm going to

talk about later. Very important aspect for both soundness and privacy in this. But let me explain a little bit more what that assaulted hash is. Right? So it's that string right there. And a salted hash is essentially a SHA 256 hash of a pre-image. That pre-image includes a lot of encoding to essentially document format stuff. Importantly includes this salt which is a random string. It includes the name of an attribute which in this case is age over 18. That's an ASKI. And then of course the value of that attribute which in this case is F5 which is essentially the Seabore way of saying true. Um so if you hash this string you get this particular string and then for all the attributes you'd like to assert about an

individual for example address first name last name uh including the image the portrait of that particular user they'll all be salted and then essentially included this credential has for example 34 of these attributes in the salted hash format. Now, if we go back to how this protocol actually works, when you go to a website, they'll make this request to your browser or your phone and essentially your phone will respond with essentially this MDOC right here, this document right here. Okay? Which basically has no attributes about yourself right now in this form. There's nothing really disclosed about you. And then you'll give a pre-image for one of the attributes that you'd like to disclose. uh and of course the relying party will hash this and make sure that the hash right here appears in

this particular list of attributes that are in that document. Everybody make sense of how this works. And of course the purported guarantee here is that uh if I essentially give you this uh document I can sort of selectively disclose the attributes that I want to um and there's some privacy afforded there etc. Okay, there is a problem though. A key concern about digital credentials is the problem of copying credentials. So, it's kind of hard to copy the plastic card although people do it all the time. Uh but there is some expense to it. A digital document though would be very easy if it was just stored on your phone uh stored as a file that you could kind of airdrop to somebody else. Then that somebody else could presumably uh take all of the attributes

of you and use them in all sorts of contexts. And that wouldn't be great for the soundness of any identity scheme. So the designers of this uh protocol in order to defeat this copying credentials problem. Okay. Uh they impose another constraint on the document. It's known as device binding in the sort of this field. And the idea is you'd want to tie the digital credential to the phone. And every single state issuer uh that cares about the identity any sort of high assurance issue in identity use case uh basically mandates this type of thing and uh it's it's a major constraint on the type of deployable ZK that we can actually use that's that you'll see essentially is why we can't use many of

the legacy schemes. The way this works is to prevent users from sharing credentials. What you do is when you issue the credential you involve some piece of hardware on the phone in the issuing process. So typically when you essentially enroll yourself there are two things that uh the issuer requires. First your phone uh uh has a secure element some sort of like piece of hardware uh that's tamper resistant and hard to extract keys from uh that all modern phones like those and all the ones you have here essentially have. Uh and uh you ask the secure element to make a new public uh uh signing key and essentially it stores the secret key in the secure element. It gives you the public key. Uh you then essentially the

the issuance procedure takes this public key. You make a bunch of selfies like live photos and use kind of the phone hardware to kind of make sure that this is the real person in front of the phone by asking them to move their head up and down and around. Uh takes a little video of you in a sort of selfie and so forth. Uh as well as your login information. You take all of that as well as the device public key. You send it to the state issuer. Uh the state issuer essentially has all of your information on file, your driver's license, your previous one. They make sure that the person in the selfie is equivalent to the person essentially whose driver's license photo they have. They do that through a variety of mechanisms. When they agree it's the same person, they then say yes to this thing and they sign

that MDOC kind of like uh they essentially put all your identity attributes into a form like this. They sign that. Importantly, they include that device public key in this yellow part of this. Okay? and they sign that and they then that information gets sent all the way back to your phone and stored essentially in a secure storage on your phone. Okay. Now, what is the problem with this? Any changes to lower levels of a phone, the hardware layer or the software layer above that that access the secure element, they take many, many years to essentially filter through the network. Right now, those phones only support two kinds of signatures, RSA signatures and ECDSA signatures for a very specific set of keys. They don't support by linear

pairings. They don't support lattisbased signatures. Uh they they have very limited number of functionalities that they basically approve. And that's a big problem for using any other kind of ZK system. Uh because ultimately let's get back to the problem. How do you assert this now in reality with all of the device binding checks in place? So what again I told you the previous request is are these three attributes and essentially the response is again the MDOC the pre-image and essentially a signature by the device public key on this particular knots that was sent in the first message and that is essentially how uh and then again of course you verify the signature of this MDO by the state you verify the signature uh of this transcript by

essentially the device public key that's in this nons and then you verify that essentially this attribute uh asserts the uh this this pre-image asserts the attribute that was claimed. Kind of all make sense. Okay. Now, there's a big problem. The privacy problem with this scheme is that the MDO now essentially contains a super cookie of your phone. This device public key, uh if you were essentially given one MDO from the state and you used it all across the internet, this would be exactly an advertiser's dream. They would use this to track you everywhere you went and made an assertion about yourself. we've learned our lesson from this type of thing. This type of tracking is essentially most humans don't like it and if they were to vote, they would vote not to have this type of thing. And so inadvertently

through essentially the problem uh the the goodwill of a bunch of people in this identity community who wanted to solve Erica's problem and essentially make it so that she doesn't have to carry that plastic thing around anymore. They inadvertently created this privacy problem. Okay? And just to be a little bit more clear, here's how this problem works. So if I was given some sort of MDOC from one state and and essentially I showed it to one service provider and showed it to the other service provider, right? They would both have this exactly this device public key to prove that this was actually the credential that was issued to my phone and not something that I copied uh and so forth. Now they would essentially link and essentially be able to create a profile of me of every place I went on the internet and asserted some quantity about myself. Uh

and that would be problematic. Now, the natural fix of an engineer would be like, "Well, these MD dodocs are cheap, so let's put a thousand of them on the phone and make you use a different one with every single website that you do." That's currently what the status quo is. There's still a problem. What is it? >> What? >> More than a thousand websites. >> Well, yes, there there are more than a thousand websites, but essentially the algorithm, the answer to that is like after I use my first thousand, I get another thousand. the bigger problem. So, it's not just that we're worrying about websites colluding. We're actually worried, perhaps even more worried about the issuer colluding with the service

provider to figure out who's doing what. And I may not have been worried about this in the past, but today I'm very worried about it. I think it's a very serious problem that uh if you're using some identity to get some sort of medical service online or do anything that you may consider to be out of norm uh and then later on a government subpoenas a website to say show me who came to your website. I think that's a that's a that's a chilling effect on what people do. So I think this is a big problem and this is uh this problem is inherent to the device binding mechanisms that are currently deployed in these legacy identity protocols.

That's the problem we want to solve. Thankfully the right zero knowledge system can solve all these problems. Yeah. >> So you're saying the device binding key that you put there across all of these tokens will be the same thing and that's the issue or >> you can create multiple device public keys. So that's fine. You can create a thousand keys on your phone and have them separate. The token itself is linkable. >> However, the issuer will always know this token and the issuer will be able to collude with the relying party and essentially figure out who did what. >> So there's no like serious memory issues when you do like thousands of these on the HSM or anything.

>> There is. So let's let's assume that you can do it. >> Yes. Yeah, it is. >> Even if you could do it, there is this power. >> Okay. These HSMs that issue these things are actually we'll see we'll see in a second. They're old school legacy devices and they don't support high TPS. So that is a problem at scale as well. But let's assume you can as as Matteo said. Okay. So the right CK systems can do this. However, uh I know this community is very familiar with Z knowledge. There are a few differences between zero knowledge for this particular problem that Matteo and I found ourselves in and essentially what the rest of the community works on. In particular, this is a big one. This is kind of a flipped sense. In all of the blockchain work, everybody talks about minimizing the verifier time of a proof

because that's essentially the that's like essentially one of the major constraints. Here it's the opposite. It's really a user's phone that is a small prover and essentially a powerful verifier. The relying party website is basically run on a server and we don't actually need succinctness. What we do need is some sort of performant CK system uh that sort of works uh from this engineering perspective. And again, a lot of this talk is about finding the right engineering trade-offs, uh, less so about pushing forward the science of zero knowledge. So, here's another sort of wishy-washy point, but it's important one, okay, which is that people's and standards coordination things that essentially theoreticians and like scientists kind of completely ignore.

Uh, that essentially the the effort required to get people to agree on some particular standard that should be zero. However, it's not zero at all. In fact, it's enormous as I've basically learned and uh and and that coordination is essentially a finite resource. You can get people to coordinate on this and then they won't coordinate on that. And so essentially, you have to pick the battle uh that you do there. And that seems like a totally ridiculous sort of non-scientific statement, but it's in fact very real. And as a result, the outcome of this is that trusted parameters we believe are going to be very difficult, I would say impossible to deploy in this scenario. And for example, you have multiple jurisdictions. Could you get all 50 states in the United States to agree on essentially a large cryptographic

parameter? Could you get the US and some other states and like like European nations? Could you get the 27 European nations? Could you get essentially the hundred countries that kind of uh are involved in this ISO standard for identity? Could you get them to agree on some half a gigabyte uh public parameter? And I'm not sure you can. I don't think there's anything in our DNA that prevents it, nor does physics prevent it. But it you know it's sort of a human collaboration problem. The other important thing that it's also hard for scientists to kind of look over uh is that essentially people have been working on these identity standards for a long time and they are essentially very emotionally tied to what they have done in the past and they might have made some subtle distin you know

decisions about how they implement schemes that I'm not aware of. However, those schemes uh essentially that have been deployed and so forth are hard to uh surp even though it might like save 3% of like web traffic if we do something better. I think it would be impossible to deploy. And that's the same sort of thing in this scenario. And finally, this consideration issuers are very limited. So it's very hard for state governments again not scientific point it's like why but it's true issuers uh will have to they they currently have uh sort of secure hardware for deploying these credentials be very hard to

replace all of that and importantly I don't think that we should rely on issuers like these to be highly available so protocols that we use should not require issuers to scale to o of internet activity they should not be involved in every flow that goes from a user to a website because I don't think they'll be able to scale to that. So again to the point of issuing a thousand credentials right that is internet scale that is like how many websites are visited by how many individuals like individuals times number of websites that they visit right that's internet scale activity I think that's too much for them to basically do it's better to find a solution that is only o of number of users work

and uh in particular you don't want to have them on the online flow of any test and certain zk systems do require uh that type of thing And that's you know probably not easily deployable. Here are some other things that we figured out that like some organizations uh that we talked to when we had original versions of this solution they were unwilling to certify or deploy systems that used uh elliptic curves in them. So if the zero knowledge system used elliptic curves uh they thought that that was not something that they would want to invest engineering effort in certifying and deploying because of their postquantum security concerns. Now the people who won the RWC uh prize this year, they're essentially the authors of the general

number uh number seieve u number field civ essentially the best algorithm for factoring and for also computing discrete logarithms uh today and all of them basically on stage proclaimed they didn't think that they would see a quantum computer beat their own software at factoring in their lifetime and so then these are the experts that I would basically put my money on on evaluating this stuff. And nonetheless, organizations are more conservative and and don't want to do that. And finally, this last uh constraint is that uh this reality of engineering basically there there might be some optimal techniques that essentially are too complex uh and don't give a user benefit enough of a user benefit to deploy. So that's kind

of one of the other considerations in building the system. I mean the obvious question about the first bullet point is the legacy signatures you're proving are >> no I know there's a deep contradiction which is that legacy requires ECDSA and that requires ECDSA and yet the zero knowledge layer that they want to apply to it uh they want that to be more resilient than the legacy scheme you can see it either way like you can say this contradiction or you can say well if you're forwardlooking then eventually you'd change the legacy signature scheme to be some sort of like postquantum system and then hopefully the zero knowledge system is like robust enough and ours is in order to essentially give proofs about now lattisbased signatures or whatever other signature scheme is

taken. However, I can see the other the counter argument is just as easy to fabricate and to to to argue. So we again make the claim that the right ZK system is the right one and uh we use the second oldest recipe. It's the Justin and I wrote this Hyrox paper. is essentially the recipe from that paper. And essentially this second oldest recipe is like you run some interactive protocol to produce a transcript interactive protocol for the computation that you'd like to give a zero knowledge proof for. You commit to that transcript and then you give a specialized zero knowledge proof for the simple language that the commitment contains this transcript and the IP verifier when run on this transcript would have accepted the computation. And so I think all of

you understand any questions about what that recipe is. Essentially all you need to do to run this recipe is pick the interactive protocol, pick the commitment scheme, pick the zero knowledge scheme that you use for that. >> Yeah. >> I guess important point to point out here is um the the benefit of having the IP in there is the transcript is shorter than the original state. >> Exactly. Yeah. Yeah, I mean of course you can pick an IP that's just as long uh and you can make the null, you know, you could essentially just make it the circuit itself and then of course that recipe still works. But the whole point of this thing uh which stems from like our work is that uh essentially we pick this sum check based protocol or GKRbased protocol. We pick uh for the

commitment and zero knowledge system we picked Lao in the Hierx paper we had an elliptic curve system with bulletproofs in there but that had that previous problem. Here we use Lero. a very simple mechanism very easy to implement and very fast for the problem sky sizes that we encounter over here and uh that's essentially the recipe and again if I were to give you some sort of highle map of how this protocol works essentially you commit uh so if you want to prove these statements right here f is a function x is the public input w is the the witness the private witness uh you would essentially have the prover use lao to commit to essentially the witness as well as some pad. The pad is what we're going to use to quote

encrypt/comit to the sum check transcript. We then run a sum check or GKR whatever layered sum check type pro proof. It's slightly different than what GKR has stated but um we run this protocol between the prover and the verifier. And here when the sum check sends some message we actually send the message exor the pad some sort of commitment to this message. And when the prover is uh when the verifier is asked to send a random challenge uh essentially we just um uh we just uh we send a random challenge and we of record the transcript that we receive here. We don't verify it we just record it. And then the final step is that we use the Learo proof system with respect to that commitment in order to prove that essentially the sum check

verifier uh on the transcript t and on the witness x and pad. So pad is used to decrypt the transcript, check the transcript with respect to the public input uh and the commitment that essentially would have returned true. So that those are essentially the the three steps and now you can sort of in your head figure out how we engineered this type of thing. We built the harrow, we built the sum check and then we built a way to make circuits and we kind of just uh glued all of these mechanisms together into a proof system. Now I'm going to talk about sort of the results like uh why the scheme is working and what its performance metrics are. Again, I'm very interested in coming here to hear about your feedback. We had this talk with Justin this morning about other techniques, Vomi as well. You've

worked in the space um on how to use other techniques to possibly improve this at low engineering costs essentially, right? Um okay. So, yeah, of course, our scheme works for legacy. It's uh deployed in Google Wallet uh in a dog food way that's like slowly ramping up like from you know 0.1% of the phones or 0.1% to it'll ramp up across uh several across a large time frame. It'll ramp up to make sure there are no problems and um this scheme very important is it's going to be robust to new requirements. uh I'll sort of get to that towards the end of the talk with like things that people have asked for then of course we can easily produce and this may not be true for example with other schemes uh very very easily again

some novelty aspects like uh I would say that there isn't much cryptographically going on except for the fact that we can kind of uh we can divide the verification task over multiple fields and we use a very simple MAC trick in order to essentially ensure consistency of the witnesses used in different fields when we do different uh proofs That's one of the sort of techniques we use. We've optimized many of the circuits. We've done a bunch of FFT optimizations to make this run very fast on the phone and for the fields that we care about. Uh it only relies on SHD6 and we use this quadratic form type of it's kind of from Justin's like early early work on matrix uh matrix verification. It's that idea that a quadratic form you basically get for

free and in fact many of these circuits can be smaller uh when when expressed as quadratic forms which means that the sum check is over a smaller number of variables. These type of things which theoreticians don't care about because it's like changing it by like five or six% or some 10%. Uh but but make a big deal here. One idea is like again when Mutu is in the audience about why do we use a Leo on some check versus leero itself because Learo is pretty pretty simple and it has a square root size complexity and here is essentially uh the big idea here with Learo you have to commit to every multiplication that's done in the circuit that's kind of how it works you commit to the input and output of every multiplication gate in your circuit and that's then you write

that in a matrix and then you sort of do the the standard techniques for uh approved systems and with layered leero applied to this layer sum check all you have to do is commit to the inputs and then commit to the sum check transcript for that particular circuit and again we're using age-old technology like this uh layered thing maybe there's some uh better ideas but the point is that this thing is much much smaller than this matrix okay and the big cost or at least before we do this optimization a big cost is essentially committing to this transcript and you know NT essentially is this nonlinear this is a quasi linear algorithm and it represents a bottleneck especially when we're doing this on the fields that we need to do that we need

to work on so I'll give you a particular example here verifying an ECDSA signature I told you those are legacy things you have to do that the verification algorithm I showed you two slides ago involve two verifications of this this is essentially the small set of steps this step four is the major one these are range checks this is the big equation that you have to verify uh which essentially requires a uh exponentiation multi-exponentiation with three bases and three scalers. Okay. And uh other schemes take a long time to do this. E they try to simulate the math uh or they do something else and uh of course with us we we verify this equation in the finite field of P256.

However, that finite field, if you look at its factors minus one here, uh you can see that it is not friendly to the number theoretic transform. In particular, it doesn't have enough roots of unity here where you can do an efficient uh entity. However, its quadratic extension does. So, essentially, if you just take the quadratic extension, you have this 2 to the 97 term, which gives you plenty of roots to do all of the work in. Uh so, that was our idea for 256. SEC P does not have this problem. brain pull. Many of these curves don't have this problem.

We have other entity techniques that are in the works here uh for how to do that. Previously, we're using a newspr uh compute essentially read Solomon encoding. Uh but now we have a slightly better mechanism. However, you'll see that because of our sum check techniques, these these uh these techniques of fast making the FFT slightly faster, they don't really affect performance anymore. Uh because the size of the input in the sum check pad is much much smaller than the size of the circuit. I'll give you some concrete data, but this is how we actually do it. Here we go. So here's uh essentially the ECDSA verification I

told you takes about 23,000 in terms of our quadratic form uh approach which if you express fully as a circuit as multiplies and pluses it's about 50,000 uh terms there and the number of inputs is a factor 50 smaller and so uh not all of these some of these are additions obviously I don't know what fraction is multiplic yeah at least this fraction is multiplication you have at least a 23x reduction in the size of the commitment that you need to do if you handle it our way instead of just with pure laarero or some other technique um some univariate technique when we actually run this uh essentially if we want to give a zero knowledge proof if we want to give a proof of knowledge of RNS a signature for uh a message E and with respect to a

public key PK this is without hashing E uh essentially on a pixel it takes about uh 80 milliseconds to produce a zk proof and it takes about 8 millconds to verify that proof. And this is in contrast, this compares to about uh you know 140 seconds for previous techniques that were using out of field math. Uh and there are some recent papers that still take about uh you know 15x uh 10 to 15x um overhead versus this particular technique. And of course, if you run this on a faster hardware, like for example, not this one, but my Macintosh, uh it's it's even it's slightly faster than that as well, like maybe by a factor of two. And this is about what it

takes to run on a like a modern iPhone as well for SHA for SHA 256. And you'll see that eventually our MDOC circuit is dominated by this particular task. Um if we want to prove that we know in zero knowledge that we know the pre-image of a SHA 256 uh for an NB block message end block meaning the number of times you have to apply SHA then essentially we get between like 11 milliseconds and like 286 or you know between 20 and 500 on the phone uh on a p this is a Pixel 6 Pro so it's like a four-year-old phone which is where we did all our benchmarks. Now I realize that was a mistake trying to be a little bit too fair. we should just benchmark on the latest hardware and and win the numbers game in contrast. So what I wanted to

show you is exactly uh the point I was trying to make theoretically which is that even for these size problems the fact that we reduce the commitment size uh by doing this layered sum check thing uh you know here it takes about 11 milliseconds or 20 milliseconds to do one block uh if you use La Hero so we we've implemented La Hero with exactly this apples to apples type of thing and if you just use La Hero uh essentially it's you know for one block it's about 273 milliseconds just to make sure that our imple implementation isn't off. They wrote a paper, a follow-up paper where they use a smaller field and they use multiple threads. Essentially, we this is all singlethreaded and their their numbers are about the same as ours. Uh so essentially it shows you that the the

it's accurate. Essentially this 26 can be very very easily described by just counting the number of uh I don't have the numbers here but uh if you count the size of the commitment essentially this perfectly explains the difference in performance uh between these two mechanisms. Okay so yeah if you run this on a Mac it's it's even faster. That brings us to like how does the legacy protocol fully work. Okay, so again we have to do all of these five steps and if I were to write essentially the ZK theorem that we want to prove for this particular application it's this that if you're given these public values for the public proof then there exist these witnesses right here which is like the actual MDOC string several hashes

several values in the field several nonses several times etc and then this is essentially the set of predicates that we want to do we have to hash the big document that turns turns out to be the most expensive part of it. We need to verify a few signatures again the one from the issuer and the one from the device public key. Uh we have to uh essentially parse the document and make sure that the age over 18 attribute is set to be true. Uh we have to compute some more hashes and we have to check essentially the validity of the credential by checking doing range proofs of the time of day the time of the current proof. That's why this time is taken as a parameter to the proof and making sure that that value is essentially in the middle of the validity period of the credential. All

of that stuff is easy. This one is the most expensive part. I have a demo. So what I'm explaining here is like this is a phone. That's a website. And again, we've through the engineering process. It would not work if this didn't work. If you're on the computer and you want to So here we go. We have it working now. The time to connect so forth. So there we go. It's bringing up the wallet procedure. you have to authenticate and then the time it takes for essentially your device to set up a Bluetooth connection and wireless connection and so forth. Uh in that time is the time it takes to make the proof is is essentially um hidden. Um so what am I trying to say? This flow requires a few things. It certainly requires human input because you have to use remember

there's a secure element that you have to authenticate yourself to before you can actually produce that device public key signature that requires either a phone a face scan or like a fingerprint scan that's on the order of seconds. And then the connection between the device and the and the and the computer and so forth is on the human scale as well. And so this proof on the Pixel 6 Pro takes about 1 second. On I think the latest iPhone it's like maybe 300 to 400 milliseconds. and it essentially gets uh washed away in essentially the rest of the the the procedure.

Um okay. So that's kind of what the current deployed scheme is. We Yeah. Question. >> So I mean so would you say proving is fast enough and we don't have to make it better? >> Yes. Proving is generally fast enough. Uh we were told 3 seconds was essentially the uh time budget and we were essentially there for a long time. We've kind of pushed it back. there is uh essentially larger and larger credentials essentially tolerating what people are imp what people are deploying um tolerating the the silly things that people might do is essentially the the cushion that we would produce by optimizing this and that is a very important engineering consideration.

We'd like to build it so that whatever silly decisions might be made without our input our system will still work. Uh so that's why we're focusing on optimizing and doing better. But yes indeed the essentially the performance budget is now well within acceptable for these these scales. >> And how how about proof size? Do you want that smaller or is it small? It's small enough. >> So the proof size right now is about 400 kilobytes which is acceptable because what people are currently doing is sending 3 megabytes. Uh so that works uh even at the scale we're talking about.

However, smaller proof size is always better because again in-person presentments that go over Bluetooth and so forth, uh 400K still works in that particular context. If you've ever air dropped a photo, then you know that that works. Uh however, that is a uh essentially a vector of unreliability that we'd like to essentially remove. We don't know how to get the proof substantially smaller in the hashbased regime because you're essentially opening up a bunch of Merkel paths. Uh so that I think is a constraint. Uh but you know and of course excellence is always if there's a clearly a better approach to this and I was excited about the kind of things you said this morning then we'd want to try to get that in

before this stuff gets locked down. Why? Again >> can I say something? You know the other reason for looking for a faster prover is that we don't know what will happen with the postquantum signatures and uh those will be more expensive and we don't know whether this will work or not. >> Yeah. >> Yeah. They could be they could get cheaper. Some of the sign postquantum signature schemes are mostly like matrix. >> They're definitely matrix vector except they're very big like at least 27,000 uh >> uh in one dimension, right? Like uh yeah in yeah in terms of bits. So yeah maybe yeah uh okay uh some of the other features we

want to talk about. So these things came up after and there were things like aha but did you think about and then of course since we had the flexibility of the circuit model and this ability we were able to essentially do all of this if you applied this to something like BBS or other you know u you know custom bespoke credential schemes and so forth uh they could become problematic. I'll tell you the most important one is this revocation one. Okay. So I think of verification of like well if you have a short validity period if you issue your credential every 30 days or something like that maybe that's good enough right however that is not good enough for many use case. You lose your phone you want to you know immediately revoke those type of things. Uh someone has lost their driving privilege. Uh maybe you'd

like to immediately revoke their ability to drive. Uh those are things that people have wished that they can do even though today you cannot do that. You essentially revoke someone's driver's license. They keep driving uh essentially until they get pulled over. Right? that that could be months or years. Um, however, this is maybe one of these things that like if we have a digital credential system, maybe we should do this revocation. So, there are two ways to do revocation. We've studied all the schemes out there. One, you could prove that you're on a list of good uh certificates. One, you can prove that you're not on a list of bad certificates. And it turns out that this non-membership on a smaller list turns out to be uh substantially uh easier and more efficient for the whole system. Uh there is like some standardized way to

do this. They have this identifier list or status list. Identifier list is essentially a list of all the good credentials. Status list is a bit vector. All of those type of things. Those are related ideas but just different encodings. Here's what we propose. You take your list of revoked credentials. You sort them by identifier by which you've revoked them and you essentially sign consecutive uh values of this particular list right here. So R1, R2 like this. You sign R, you know, R2, R3, R3, R4, etc. So you have a list of signatures of these pairs and then you have every valid user essentially download the particular bucket in which their credential sits and essentially then you give a zk proof uh of

non-revocation meaning that you know a signature on a particular pair and your ID sits exclusively between those R3 R4 between the left and right ids of that type of thing. So what this boils down to is that the zero knowledge proof that you give for revocation is constant size. Essentially it's a proof of one signature of a left and right pair. You also have to include this version identifier in order to make sure that you don't use a previous uh list of uh uh of re revoked list. You have to use the current one etc. Um however uh if for example uh only 1% of uh of the credentials are revoked at some given time then the size of this data

structure is 1% of the entire user base that's good. If you don't ever revoke for example the size of this is zero and essentially add zero cost to very little cost one signature very you still have to do this proof but it's again like we saw like between 20 and like 60 milliseconds added to a particular proof and it's uh very easy for then for people to deploy. Now people have commented about the cost of signing these particular pairs versus the cost of signing one big list. Uh so there are some costs on the issue on the re revocation uh authority uh that uh that are not captured here but this scheme uh we've implemented and it sort of uh solves this particular problem. More importantly the phone only has to download one bucket one one particular

witness uh and essentially those witnesses can be packed into buckets. So essentially the the metadata of who downloaded what and when can kind of hide essentially uh your identity among a larger bucket. Uh, very good. By the way, the relying parties don't have to download anything. Yeah, go ahead. >> Uh, I have a question about the revocation proposal. So, suppose my ID gets revoked later. What prevents me from giving the old proof? >> Yeah, that's what this version number is right here. So, essentially you proof uh so relying parties essentially just need to have the latest version number of the revoked credential and they can pick that based on policy. So maybe I only care that your credential was valid within last week or let's say or last

month for example. Uh then essentially all I need to do is use a version right here. And this proof right here I I neglected to add this essentially. But you also have to say that uh the version of this this this version is signed. The witness that you're using essentially is greater than or equal to essentially a public parameter which is like what revocation list the relying party wants to use. Does that make sense? So, you can't use a previous one. Uh, you can't use an older one. You have to use the the one that essentially the relying party requires, one that's newer than the one that the relying party requires. Make sense? There's a different format called Jot. We can support that as well. Uh, pseudonyms.

So, for example, you you might want to create a cryptographically bound pseudonym. You might want to restrict a user to only producing like two or three accounts on a website. And you can do that using this technique, this old technique of essentially having a secret attribute essentially signed into your credential and then generating a a NIM by essentially applying some sort of PRF against the secret and the current context. Context could be the URL of the website or URL, date, etc. Any unique string that identifies the interaction.

This is almost zero cost. Hiding the issuer. So proving that you have a deal from a US state essentially is like an or proof. We talked about this a little bit earlier and that just means that you know in in the issuer statement the MDL is signed by one of PK1 PK2 PK3 you can put a thousand public keys in this. Since it's a public parameter it does not uh change the size of the proof. And since it's an or essentially with the simple mucks with the you know less than n gates you can essentially mucks out the key that you care about and just use that one. So it uh it adds very little complexity. Now hiding the issue in other schemes like BBS and so forth, it's not clear how you do that type of thing. Um okay. Yeah. The next major

hurdle for us is getting regulatory approval which is essentially talking to a bunch of uh cryptographic boards and so forth. If you guys have any insight into how to do that or want to help us out, that'd be great. Um, the scheme is uh mentioned in this uh EU digital identity wallet web page. It's also essentially the chosen one for the age verification mechanism that Europe is going to deploy uh essentially as soon as possible for uh you know basically agegating content on the internet. I was going to spend some time talking about alternative scheme. So Vampsy worked on the crescent scheme. is a very very clever idea to rerandomize an expensive proof. Uh the reason we essentially don't think this will work is

essentially requires a trusted parameter requires that collaboration which I think is a finite resource that we've basically exhausted among humans and uh it still requires a c some sort of circuit based thing for the device binding. The regulatory approval for this type of thing would be again u just as costly. it's two schemes instead of one and essentially requires a bilinear pairing which is again some sort of postquantum. So there are no real reasons except for engineering ones and human ones for why we think a scheme like this can't work. Um we don't think a phone can store these different type of parameters. There's another uh longer term scheme the BBS plus family in the literature. This was the anonymous

credential scheme for like 20 uh you know 20 years or so. Essentially the it was a signature scheme that was optimized for a a simple zero knowledge proof to prove attributes about the uh uh that that have been signed and there have been some many suggestions like this uh one of these suggestions. So either you have to use a pairing with this family there's some idea that doesn't use a pairing but that as a result it requires the issuer to produce requires the user to call the issuer every time you need to produce a proof. You could do this in a batch setting and so forth, but it's essentially we don't think that issuers should be involved in internet scale work. So we don't think it's it's reasonable. Fundamentally though, we think we have another uh problem with uh so yeah this the reason

there's this entire no phone home community which uh s sort of privacy advocates have sort of signed things that uh so should take a look. Uh it's very vague but uh they basically don't want identity protocols that quote phone home whatever that means but uh we think it yeah anyway let me try to talk about the BBS scheme and why we think that there's some problems with it uh that can't be deployed and then we'll talk about questions. So basically the idea is traditional signatures essentially hash a message and BBS instead signs this vector of messages like M1 and through MN and so forth. um each of these messages is some attribute that you want to essentially sign and sort of uh you can give some proof that for example the i component of that vector is like vi that's kind of what the bbs

scheme lets you do through a sigma protocol the problem is you do not hide the particular index of the attribute that you use that is like well known it's well written and so forth and that's sort of a hidden problem with deploying this so for example if the issuer issues credential one with the order age, name and zip and then issues credential two with name, age and zip. And if I get a proof that the user was uh sort of age over 18 was true. However, here you disclose attribute one and here you disclose attribute two then you can easily sort of distinguish these two things. You can easily violate the unlinkability security property. Does that make sense? If I reveal the index

in this proof which is a property of BBS, you have to reveal the index. Then if an issuer uses different schemas for mapping attributes to uh indices then there's a privacy loss. It's a very subtle issue, but something that will get glossed over. And in particular, if the same issuer decides to augment their schema and essentially interjects some attribute in the middle of their thing, all of them get shifted down and they get different numbers, then essentially a relying party will be able to distinguish between, you know, today's uh people who and then yesterday's people, right? So they'll still be able to distinguish between user sets. And this is a subtle issue to argue about and it's a very important engineering practice. Yeah.

>> Sorry, but like if the number of attributes were different, it would also affect all things, right? >> Yes. So you this is assuming that you pad >> you're saying you would pad to like a maximum number of attributes or something. >> Our our thing does look up into a dictionary >> of an arbitrary size up to a maximum size. >> Okay. So you pad to a maximum size. >> We we pad the bytes. >> No, wait. What are you talking about? Our scheme or the BBS scheme? >> I mean I guess any scheme, right? Like the verifier needs to know the number of attributes. >> Yes. The verifier needs to know a bound on the size of the credential. That's true in our system because we give you a number of bytes. We say the credential is at most 2,231 bytes and the attributes exist in them.

>> So now if an if an issuer adds another attribute that bound would increase, right? >> Uh no, I mean the like the scheme is defined by a circuit size >> and essentially we rely all we require issuers to essentially that's true of any scheme with the circuit. You have to have a certain input size that everybody abides by. If your input's larger, you simply can't fit into a circuit, >> right? So then wouldn't you also be able to make some kind of upper bound in the BBS thing? >> Well, there are two different issues. The number of attributes. Let's assume that in BBS you pad everybody. Say there are thousand attributes. I don't know what they are, but everybody can expose at most 1,000. The issue I'm talking about is the way you map the attributes.

>> The ordering of them is what you're saying. >> The the mapping. Yes. So >> whereas in our scheme, it's a dictionary. We say, you know, doesn't matter whether Okay. Okay. Now I think I understand it. Okay. Yeah. >> So either all issuers in the whole world have to use exactly the same schema. Again, something we don't think that people can agree upon or there's going to be some sort of privacy leaks throughout the system that are going to be hard to reason about. And randomizing the schema doing any sort of type of thing does not help this. You e you have to use this you have to use a different scheme. Again there are other attributes like how can you hide the public key of a BBS scheme? How can you hide the issuer? All of these things require essentially extra work that we haven't

figured out how to do. Of course, this thing is well it's well documented that you don't uh the indices that are discloed messages are public and so forth. It's not like we're pointing out a new bug. It's just uh when you deploy this scheme it this type consideration is going to be uh and of course the biggest problem the biggest elephant in the room is how do you do device binding with the BBS plus credential. this scheme, this phone does not support BBS+ and so there are a bunch of proposals on how to do that and there's some new clever cryptography of linking fields and so forth. However, this is a big problem. Uh one of the problems for example this BLS curve it's this size whereas P256 is this size. So for example the standardized curve that

everybody uses for bilinear pairings now that's not big enough to support all uh to essentially embed the public key into a BBS credential. technical detail we can get into but uh we we have a number of flaws which prevent this scheme from essentially being deployed at scale. Now I want to basically end up end the talk and like leave a few minutes for questions and again uh I'm hoping that our active discussion this week will be on new techniques we'd like to learn about for proving things like ECDSA and shot 256 etc. But any any questions?

>> Are there uh you know like uh some people arguing in uh for alternate approaches to um the proving credentials. Um and the world somehow has to pick one. Um you know there's like a BBS plus camp and a there is >> and a snark camp and it's not clear who's going to win or something. So the the basic uh the situation right now is that um so uh many some group of people who worked on BBS think that that is the simplest uh best way to do it. They have not implemented the system at scale or tried to put it on a phone or basically resolved how you do things like how do

you do revocation with BBS because again you have this these our trick doesn't work. How do you hide the issuer? How do you do all the validity proofs with uh you know comparisons? Of course, all of these things exist with inner product arguments and bulletproofs and all these type. But again, the system becomes more and more complicated. It's not the argument is that the original BBS signature scheme itself is very elegant and simple to reason about. If you ignore the complexity of what it means to implement a bilinear pairing, which I've only met three people who really know what a bilinear pairing is, >> um, if you ignore that, nonetheless, the original signature scheme is simple.

However, I feel that the complexity of the entire deployment is ignored by those people. Uh then there's us. We like to favor this layered approach which everybody has deployed this stuff. They can pick when they want to deploy zero knowledge just by applying it on top. It's deployed at scale with engineers at Google who have kind of built the system around it uh and you know goes through the process of engineering there which is pretty strict and uh and has all of these particular benefits. However, the downside is the complexity of verifying circuits. That's kind of the fundamental. So of course there's understanding our ZK proof system which I feel only requires understanding uh essentially the leero essentially it's a form of selective

disclosure instead of giving a pre-image of a exact thing you're giving a pre-image of a Merkel tree of a read Solomon encoding of the witness and so there's like a few extra steps but essentially the same technique is involved and of course there's also involved you know the the sum check part of it as well as the circuit design part of it. Those are all layered complexities which the average engineer and the average regulator may not be familiar with and we have to convince them that this stuff is is legit. One of the things I was talking about your intern last year who was doing like a formal verification of some check and that so those kind of tools like really help in proving that like it's not humans verifying this proof it's actually these steps again gluing it all together and proving that the whole

system is sound I think is really a long-term task but that's where the two camps sit. Then there are people like the crescent system which uh uses like a hybrid approach you know they get the performance through pre-processing but the complexity introduces elsewhere as well as the deployability problems and uh then there are uh and there's some other schemes like um Paul at at Michigan they they have similar type of scheme um they're using Spartan uh so I mean I think that our schemes subsume theirs in terms of uh being better implementations and better usage of like layered sum checks and so forth. Uh >> and so um whatever parties insisted on a post-quantum proof system uh evidently

the uh have not BBS plus uses pairings and >> exactly no they they object to BBS plus on that. So in fact those people and that's kind of why the EU is kind of at least that age thing had suggested ours because it it checks all of those buckets of like those concerns. Uh >> okay. Do you think if uh well you you know we we already discussed that everything is efficient enough now >> yes >> it'd be great if they get more efficient and let let's say you know we just came up with like way better snarks would that end the debate or no would would there still be like a >> I think the debate's about complexity >> it's about the complexity of the approach so

>> less so than performance >> less so than performance yeah >> well also to make the professor shut up you you have to give benchmark right and if you can run this whole thing in 10 milliseconds then the BBS people cannot say anything >> okay okay >> that's true >> I mean yes one but so I would say BBS makes its argument that it's you know slightly faster maybe like an order of like 10x faster >> and I think the main argument they they feel that it's simpler and easier to verify they think sigma protocols are easier to understand as as zk however I don't I don't believe that so >> okay So let's say two years from now the general purpose snarks are you know 10x faster and the formal verification has

made a dent on them and now now the the comparison seems pretty clear like the main arguments against the snarks kind of are addressed >> are addressed and that's why I feel like this approach is has legs because I think both of those things even if the 10x doesn't happen uh I mean we already know we already know many inefficiencies in our scheme like we're not exploiting copies we're you I'd be I'd be more confidence that confident that 10x happens than the formal verification happens in in that timeline anyway in the two-year timeline. Yeah, >> that may be too late.

>> Two years is too late. >> I mean it like the the EU needs something for age verification this year and so this thing that we have works and sure there may be a version 2.0 So, but we we need to get going kind of today and >> BBS is a problem because you have to essentially if you choose that you have to change everybody's infrastructure and that's you know that's a deployment issue that's a human issue >> that'll take more than two years. >> Exactly. >> Yeah. Okay. And then in the if they want something today how I mean I guess we sort of discussed this already but like the the worries about bugs are are major worries, right?

Yes. Um so what how what are your thoughts on addressing that if if this is getting deployed you know today or >> yeah almost today. >> Well I think parts of our system like our circuits for example ECDS some simple parts of our circuits I think we can produce formal proofs for especially the algebra purely algebraic parts. Uh and I think that uh scrutiny especially by like experts people in this room uh we made our thing fully open source. We hired two companies to kind of uh do security reviews. Of course we'd like to get more people looking at it and doing the human best effort of uh figuring out

whether this makes you know whether this works. Now I personally believe that the software quality is just as good as whatever identity schemes were previously deployed. I think our system is on par with those no worse even though there's a lot of complexity going on. uh you know we've taken you you look at our thing it's 99.7% coverage with tests we fuzz we do all the best software best practices uh which you know you know but like conceptual errors are hard to catch and those require expert review >> but also I want to point out that our circuits are not as complicated as you might think right because we're not simulating a processor with memory and

we have one ECDSA we have one SHA which you can verify you know more or less exhaustively >> and we have a bunch of shifters to move to realign things and then do a comparison to equality right so it's not that complicated >> yeah okay and I guess as you add more features the circuits get more more complicated but not not in a crazy amount yeah >> all of these things are using same mechanisms that we do for other comparison right so you're comparing you're comparing integers and you're checking a signature >> yeah The real screw up will be have we forgotten a check right that should be there and yes that's very hard to test >> and I yes in certainly in our development phase we have I have

forgotten many simple checks uh which which have uh but we catch them right so thank you for your attention and looking forward to talking to you guys uh over the