Episode 363 - Bringing ZK to Google Wallet with Abhi and Matteo

Transcript

[Music] Welcome to Zero Knowledge. I'm your host, Anna Rose. In this podcast, we will be exploring the latest in zero knowledge research and the decentralized web, as well as new paradigms that promise to change the way we interact and transact online. [Music] This week, Nico and I chat with Abby Shalat and Matteo Frigo. Abby and Mateo are engineers at Google and are part of the team that built the ID features in the Google Wallet product. Abby is also professor at Northeastern and both have been long-standing researchers in the ZK

space and beyond. They are the co-authors of the anonymous credentials for ECDSA paper, which is the system that is powering the ZK component of the Google Wallet ID product. This is the clearest case of ZK breaking into the mainstream by having it be used and publicized by one of the largest companies in the world. It definitely feels like a step change and this announcement has made waves in our community. In our discussion, we cover how a user engages with this system, the technical details behind the implementation and then we dive into the details of the ZK system within the anonymous credentials for ECDSA paper.

Through this, we cover the other works that inspired this construction, their unique requirements, the challenges of translating between legacy cryptography and new systems, and look at how ZK in this case has been used in its original sense, that is to provide privacy for sensitive information. Now, before we kick off, I just want to highlight our upcoming ZK hack Berlin event. This is our fifth ZK focused hackathon, and it's happening on June 20th to June 22nd in Berlin. This is part of the Berlin Blockchain Week and so if you're looking to jump into ZK and build using some amazing tools we cover on the show and win prizes while doing so, be sure to join us. Find out more at zkblin.com. Now Tanya will share a little bit about this week's

[Music] sponsor. Boundless is a universal zero knowledge protocol developed by risk zero that lets anyone access abundant verifiable compute regardless of the blockchain they're using. Boundless provides a network of nodes dedicated solely for execution, producing ZK proofs that the work was done correctly, verified onchain at a low constant cost. By decoupling execution from consensus, Boundless lets every chain keep its native security with infinite scale. Learn more about Boundless at boundless.xyz. So, thanks again, Boundless. And now, here's our episode.

So today, Nico and I are here with two Google engineers, Abi Shalat and Mateo Frigo. Abi is also a professor at Northeastern. Welcome to the show, both of you. Hi Ano. Thank you for having us. Thank you. Great pleasure being here. Nico is also here. Hey Nico. Hey everyone. Nice to be here. So Abby and Matteo are on the team that has built the ID features in the Google Wallet product. Uh this announcement just happened recently. We've all been very excited about it. So it's very cool to get a chance to dig in. You've also been behind the ZK part of that ID. They're also the co-authors of the anonymous credentials for ECDSA paper, which is the ZK system that underlies, you know, the ZK part of the ID features. So, why don't we start off with a quick

explanation of like what the Google Wallet is and how adding ZK actually adds something for the end user. What does this enable? Okay, so Google's mission is of course to organize the world's information, make it easy to use and so forth. Google Wallet's mission is to organize your personal credentials uh and make them essentially easier to use and simpler and safer. And uh your personal credentials involve three kinds. So there's like essentially transaction credentials, things you use to pay. There's identity credentials, that's kind of the thing that we focus on. Uh and then there are other type of credentials like passes and loyalty cards, etc. But it's the identity portion that we're basically working on.

And what ZKP allows you to do is to make statements about your identity in a way that reveals nothing else. So you can prove things like my age is over 18 or my zip code is 02445. Yeah. Was was Google Wallet also for credit cards at some point? That's right. That's like that's the sort of association that I made with the term. That's why like when I first saw this I was like is this to prove something about your credit card? But it sounds like it isn't really. It's kind of a new feature. It is. Oh, it is. So, as I mentioned, it's like organizing all of your credentials. And of course, payment credentials are also those type of things. So, Google Wallet does let you do all of the tap to pay. Uh, so there's like a bunch of payment transaction stuff that it supports, like

you can buy stuff and, uh, pay for stuff, uh, etc., send money to other people. Um, that's part of it. Uh, but, you know, your credentials are kind of your payment credentials, your identity credentials, and a bunch of passes like for example, your airline tickets and, uh, you know, your loyalty cards. All of those things are handled by Google Wallet and one one part of that is the identity part and that's kind of the part we're working uh with uh and and applying zero knowledge proofs to. Cool. So, it's kind of funny like this announcement came out and it got so many people in our community in the ZK community also in the general blockchain community very excited. Although as I think as we dug in we realized like it's more ZK than blockchain. Is there is there a blockchain connection under the

hood? No, not at all. Okay, cool. This is sort of where I see like ZK somewhat splitting off like just in terms of like usage and mind share almost like real this is kind of exciting to see this happening that ZK is standing on its own. While I think a lot of the research and emphasis and and financial support to ZK has come from blockchain, you know, now we're kind of seeing it entering the world in a new way. Well, uh you can look at it that way. uh I mean the original paper uh from the 1980s and a lot of the theory from the 80s to the you know early 2000s was uh using zero knowledge for privacy for privacy in the real world. Um and so I've been working on CK for a long time

since my PhD and uh you know I think it's been great that the blockchain interest has uh put a lot of you know resources and uh moved the field quite a bit in the last 15 years but I do think its original motivation was for privacy enhancing tech and you know people like my advisor Sylvio and people like David Chum been working on it for on signatures for the type of things that we're building now in GK in in Google wallet. True. So, it's almost like a return to its original goal. Yeah. Back to the roots and back to the actual meaning of ZK, which is zero knowledge and privacy.

Um, yeah. So, when when this announcement came out, like at first it was actually tricky to understand who was behind it. And I'm going to give a little credit here for to way dye who did some sleuththing on Twitter and basically discovered that the the ZK system underlying this was the anonymous credentials for ECDSA the paper that you had written. And then I want to also say thank you to Mu from Lihero who was nice enough to make the intro to both of you um so that we could actually get this episode going. So yeah, I feel like it was kind of interesting how first it was like Google uses ZK and then it was like how, what, where, like who, and eventually this all kind of became more clear to

us. It it may be helpful to give you some background information of what this project is all about and where where it's coming from. Cool. Now, for at least a couple of years, possibly even longer, there has been a lot of work on the European identity wallets. uh the the digital European wallets. Um this is a project of a European Commission to have all the member states issue um some kind of mobile app that stores your driver's license or your passport, some officially sanctioned equivalent of a driver's license that is that has legal value and it is in in all respects equivalent to a normal government document. And uh as part of that there was a lot of discussion, a lot of

concerns about uh uh the the the scheme that was envisioned lacking privacy. It would leak information about you to the so-called relying party uh to the receiver of a document in a way that allows the user to be tracked and people didn't like that. So zero knowledge was uh suggested as a possible solution to this problem and that's really the problem we have been trying to solve. So we are not really blockchain people. We've been working on this actually for a reasonably long time and we are well known in that community trying to build the European wallet and we are as surprised as you are that somehow uh the blockchain community thought that this was kind of relevant uh to to to what

they're trying to do. Yeah, I saw I saw a bunch of like crypto press pick it up as like you see you see everyone's using the blockchain and I'm like it's not a mystery and you have to dig to find out who is behind it. You know we've been quite active in that European wallet community and equivalent efforts in the United States for a long time at this point and you know everybody in in that domain is well aware of what we're doing. We've shown demos and they know what's going on. For sure. And actually the minute like looking over the work that you've done and the papers that you've released, we actually are familiar with your work in the ZK community that I'm that we've been building as well. Very very familiar.

But I think it was putting those two things together like the Google announcement and that it was you guys behind it. Let's talk a little bit about your backgrounds and kind of what got you started. Abby, you just mentioned you've been working on ZK for a long time. U Malli was your adviser. Like I'd love to hear a little bit about that. Were you working on ZK back then? Definitely. Yeah. So I've been cool like I think my thesis is on like a non-interactive ZK various constructions and uh been working on secure computation and zero knowledge protocols for essentially the last 20 years. Cool.

And Matteo, he has a very interesting background too. I'll let him uh he's like a very integral part to this project. So he's brought a lot of the engineering discipline and uh focus uh to make this system as performant as it is. So yeah. So I'm not a cryptographer by by background but I was actually a teaching assistant to Sylvia Malli back in the day at MIT. So wow. So I I know Sylvio pretty well even from before Abby. I think I've been doing all sorts of things in my life. I've worked a lot in cloud. I was the architect of the elastic file system at AWS. I was one of the people who started the Oracle cloud.

So a lot I have a lot of uh experience in building and managing and shipping cloud services. Separately I also have a an interest in applied math. So I worked in various medical devices and uh software radios and uh I wrote a FIA transform library called FFTW that is very popular and I think many people are still using it after 25 years. uh so I have a separate interest in applied math which turned out to be completely relevant completely you know necessary uh for doing this kind of ZK work so a couple of years ago I bumped into Abby and he said look I need help for to do this thing and uh and here we are I saw that you've also been writing uh chess

engines uh yes uh so if I tell you the story of my life you know we we we will never end so lots of things had you worked together before on any anything? No, we uh we had a few people in our social circles and that's how I kind of ran into Matteo and then as soon as I realized that I knew about FFTW for a long time. So I didn't realize there was a chance to hire Matteo and that that's like it's critical the the number theoretic transform as you guys know is very uh critical component of all of uh the ZK systems uh both the succinct ones and the zero knowledge ones and uh and that's also true for our system and Matteo's uh insight to these things. We

have uh we have a few things coming out soon hopefully some papers to write about uh our interpretations about some of these uh FFTs and entities. Yeah, this paper itself is is full of these gems and talking about the FFT is also on my list of of questions for later down the line. Great. So, when did your involvement with Google start? Like when did this project actually start? Uh it's hard to pick a time. We were working on something else. We were in core labs kind of a research uh aspect of Google. Okay. For a while and we're working on some other projects. I would say the application of zero knowledge like as Matteo said to the European wallet I think it's it's like less than two years. Okay. So why don't we dive into anonymous credentials and the paper that

underlines it? I mean something I'm really curious here is like how did you choose which systems to kind of like be influenced by because there is a lot of material out there but yeah why don't we just start with what it is. Yeah. So how do you choose which system and the answer is actually pretty simple. you pick the only one that works. Okay. Well, that's an easy one then. So, yes, there is a lot of stuff out there, especially in the blockchain community, but you have to keep in mind that our problem is very different from the normal blockchain problem. Uh so, specifically in the normal setup of all of of a theory of zero knowledge, the prover is uh the computationally uh powerful part and the verifier is kind of a wimpy portion. Mhm. Um whereas in

the problem that we have the prover has to run in the phone and so the problem everything you need to do needs to be optimized for pro time and if you look at all systems or most of the systems that are out there they're all optimized for verifier time uh which is not the problem that we have. The other thing that we need to do is uh this is meant for the wallet credentials. So for some kind of digital driver's license or passport that the government gives to you that is bound to the phone and it has to be bound to the phone because otherwise people can copy it from one phone to another and then the whole scheme breaks down. So there needs to be some kind of hardware mechanism uh to make sure that you can only use the

document if you actually have the phone and that's done by means of ECDSA signatures produced by the secure element on the phone. And once you start looking into that, then that's inescapable because there is a piece of hardware that does ECDSA, it will take years to upgrade all those pieces of hardware in the field if you want to do anything different. So that's kind of the other constraint. Uh so you need to come up with some proof system that can handle ECDSA. So once you actually start putting all the pieces together, there are many solutions that work and we we have assembled together a bunch of techniques that somehow solve the whole problem. I'll add one more constraint that we added which is that uh since we

knew that we wanted to deploy this uh you know globally we didn't think that there could be a trusted parameter setup. Yes. No trusted setup then was no trusted setup in for many reasons. Not first that because it would be very hard to get the whole world to agree on some trusted parameter and second of all those trusted parameters are pretty big and basically making people store a gigabyte or half a gigabyte uh string on their phone isn't something that simply can't be deployed. So that's a major constraint. You know as both of you know there are many many designs for Xernel systems or succinct systems. Some of them require the trusted parameter setup and those those are you know very small proofs and very short time to verify. So

they have some natural features but it's not uh applicable to our scenario. So that's another constraint. Got it. And actually if you think those like the hashbased ones they have larger proofs faster verification no trusted setup but I guess you couldn't use those because of this proof issue. Ours is a hashbased uh proof system. Okay. So I'll tell you the other constraint which is uh we originally um we originally started from like this hierax design which is essentially like a sum check based uh interactive proof and you commit to the transcript of an IP and you basically then give a small zero knowledge proof about that commitment. So that's roughly our design. Uh but originally we had a sort of discrete log based commitment

and we received a lot of feedback that people were uncomfortable with deploying things that weren't uh postquantum secure ah or purportedly. So there's another one that's another requirement then. So that's another requirement that came exogenously which is that people would be more comfortable with the proof system that didn't rely on an assumption like discrete log. Even though the underlying signatures today do require that, they didn't want to layer a zero knowledge proof that also required that. I was going to say that's interesting, right? Since ECDSA anyway is not quantum secure. That's right. Yeah. So although the underlying theorem, you know, still requires that that comes from a hardware restriction. Uh given given choice, you'd prefer a system that didn't

require a discrete log assumption for the zerolus layer as well. And so indeed our our system only uses uh a hashbased commitment. So we use a learo uh as an outer layer that wraps a a sum check transcript. And part of the requirement comes from the need to standardize. So remember this is a system for official use. And governments this is not blockchain your governments will need to have some kind of standard and standard bodies are really not that happy to standardize today something that is not postquantum. Yes. So irrespective of whether or not it makes sense to combine a postquantum thing with the CDSA, uh there is still the problem that building a non-postquantum proof system

requires a standardization that won't necessarily fly. So it goes back to what Matteo said, right? like uh when you put all of these things together, there's only a handful of uh possible options and then uh we think ours is kind of the most performant and the simplest and we've tried a bunch of other things from a high level. Can you explain how the anonymous credential system works? Like what ECDA signature are we verifying and what does it attest to? Good. Uh so let's um anonymous credentials has like sort of multiple meanings. Um so instead of getting into the technical weeds about exactly what that is um essentially at a very high level there are a few components we you receive or

your phone receives essentially a digital signature from let's say the state of Massachusetts where we are and Massachusetts maybe signs a document that says my name is Obby uh I live in zip code 02445 and my birthday is X and uh maybe a few other details and they sign a document in a specific document format like that. So, they also include in that signature to do what that what Matteo was talking about with device binding. Um, in addition to signing all of those things, uh, they sign a public key. And so, when I onboard my driver's license to the wallet, uh, what my phone does is it actually creates in its secure enclave, it creates what's called a device public key for which the secret key lives only in that secure element.

So, uh, essentially that device public key goes to the state of Massachusetts. Massachusetts already has my details. So they basically make a document with all of my private, you know, my identity details as well as this device public key. They sign that and they send it back to the phone. Uh so now my phone basically holds a signature from the state of Massachusetts uh with all my identity attributes and this device and a signature of the device public key. And so now let's say that Nico, you're a relying party and you'd like to check that my age is over 18. So what you do I go to your website let's say uh and you basically form a request and one of these protocols that we use today is this credman API. It's one of the things Google has proposed and it's being standardized but it allows browsers

anywhere to kind of ask for these identity credentials. Um so your browser will basically ask hey Obby please give me a um digital credential that shows that you're over 18. and essentially Chrome and my phone will basically work together to say aha here's what I'll do. Uh I'm going to give you a zero knowledge proof that I hold a signature essentially signed by state of Massachusetts on a document. A part of that document uh basically asserts that I'm my age is over 18 and another part of that document asserts a device public key. I'm not going to tell you the device public key, but then I'm also going to give you a signature uh under that device public key of this

transcript that that uh that we just negotiated. So this transcript is kind of like a nons for the the livveness of this interaction. So you can't replay these things. And so essentially that's a zero statement that I hold a signature signed by Massachusetts on a document. Part of the document says I'm over 18. part of the document has a device public key and I also have a signature by my device that using this device public key on the current transcript that we just discussed. I send you that proof back. You verify it and then all of a sudden all you've learned is that Massachusetts says that I'm over 18 and that you own the device that I'm interacting with.

Yes. You know to be more uh you know pedantic essentially Massachusetts issued a signature for Obby to a device. That device was used to essentially produce the zero knowledge proof that states blah blah blah. And it's important to notice that without ZK the device public key would be a tracking identifier because now it's your unique identifier of your phone that will if you provide the document as is that contains the device public key and then people can track you. Interesting. Uh so so the zero knowledge is precisely the mechanism to avoid this issue. Wow.

Right. And so here as a verifier, the only public data I need is the Massachusetts public key and the sort of non negotiation that we have at the beginning, right? Um and so this uh this protocol is end encrypted. So like this this transcript includes like a diffy helman key exchange. And let me add one more detail to this which is that uh it's also possible for me to hide which state I'm in. So essentially as a verifier you would you would hold all the the root keys of all of the state DMVs and basically my proof will be slightly different. It would you know depending on what use case uh you know there are several ways to deploy this but it's possible to deploy it in a way that allows you to hide which state

you're from as well. So essentially all you learn is that I have a US identity document that uh stipulates I'm over 18. But if you need to host, like going back to your example, you have the public key of Massachusetts potentially. Wouldn't somebody be able to track that? Uh, well, I mean, that's public information, right? Yeah. So, could they match that somehow? Uh, again, the public key of Massachusetts is just uh it's something Massachusetts has issued and my credential is just going to be signed by that. So, all you know, everybody from Massachusetts will have a document that's signed by the Massachusetts public key. And if you formulate the CK statement correctly, uh, the verifier doesn't even learn that I'm from Massachusetts. Just learns that I'm from

a United States. Okay. region. Hm. I wonder like the actual process of doing that conversation with the Massachusetts entity, is that happening at the moment that you're like creating this ID on the like on the device? Like you're scanning I'm assuming the what is it? NFC chip in the passport and then a conversation is triggered. So the onboarding process for how you get your digital license um it's uh you I I I can show that to you um because that's public. You can do that today but let me just describe it since it's a podcast. Yeah.

Um so it involves a few steps. So uh indeed there is a conversation between your phone and the mass and the DMV and Google is actually just used as a proxy. It doesn't learn any of this information. It just is there to facilitate kind of back and forth uh internet connections. But essentially, yeah, there's a ceremony where you basically take photos of your front and back of your driver's license. You do this ceremony that involves you to take a video. You kind of have to move your head in the right direction. It'll tell you move it up or move it down. like it'll make a random choice uh to kind of make sure that people don't replay these ceremonies. Uh and then you do all of that ceremony. You take pictures and you take a video of yourself. You upload that to DMV. The DMV of course has your

picture and has your information. So it basically looks up, you know, their version of your information. It it makes a a determination whether the person that's in the video ceremony is the same person on the DMV. And if they agree that it's the same person, then they basically issue the signature and they encrypt it and it goes all the way back uh through Google to your phone and then it's stored on your phone in a secure way using like a bunch of encrypted primitives and uh it's protected by kind of your biometric. Cool. The example you're using is the driver's license, but are you also making use of the chip?

Okay. Right. So that's one flow. Uh thank you for that clarification. One flow is the driver's license. Uh and the other flow is the ID pass which you can use your passport with. So anybody in if you have an Android phone today, you can kind of uh hold your phone to the back, download Google Wallet and hold your phone to the back of uh uh hold the passport to the back of your phone and that essentially reads information and then again there's a process that um goes back and forth through Google to an issuing party uh and then essentially a credential that includes all of the information on your passport is issued by Google and stored in your phone. So Google is the issuer and the ID pass and that actually that flow uh I I did this

the other day at San Francisco. Uh many airports the TSA allow you to use Google Wallet and your ID pass to actually in in the form of a real ID. So you can kind of go through TSA already. Yeah. Already using your Google Wallet with your ID pass. So that's kind of one of the use cases of uh was that even before the ZK incorporation that they were allowing this? Yes. And just to be clear, the ZK has not been used for that TSA application. It's uh that's just the ID pass uh that's kind of a standard identity flow. Uh because you know TSA is a high security flow where they actually need to know your identity.

There's uh there's no DK is not being used in that. But it's a reason to get Google Wallet because for those applications you can use it. Uh and then for internet applications where zero knowledge is useful uh you can also use it. Cool. I think we've mentioned ECDSA a lot and I think you slightly talked about this Nico earlier on in this episode, but like it's not quantum secure. I've understood what you've said here is like a translation of legacy IDs with possibly limited cryptography to a modern more modern ID with modern cryptography. And is there a challenge in doing that or do you just sort of wrap it? Do you just sort of like take what they have and then you just transform it and then use what what you got from that? Like is there anything in that translation that's complicated?

Well, the complication comes from dealing with the shackles of legacy, the shackles of ECDSA with the P256 curve and with SHA 256. So, okay, as a deployment, it's much better to take a legacy system that's already working and just add a zero knowledge process to the top of it and you know, it's layered in that way. So it's very easy to deploy and that's that's why we're able to get this into Google wallet and have it working this year. But the technical difficulty that introduces is um twofold. So first thing is that uh ECDSA is a signature algorithm that's specified with a particular family of elliptic curves. There are many many curves you can use. Uh the people on

blockchain use one version of a curve. We use the NIST standard P256 curve. Okay. And those curves essentially are defined by finite fields and parameters a and b for the curve. That finite field uh you know finite fields uh are wonderful beautiful elegant uh mathematical objects but they have some constraints. So for example the p256 finite field it has a property that it doesn't have the right roots of unity that are needed for performing a nt algorithm. Uh so that's that's a limitation. So other proof systems like Stark or Learo or even ours right um that need an entity that need to do a

read Solomon encoding on some sort of witness the P256 field is not a good field for that it doesn't support those roots of unity so what other people have done to work around that is they build a ZK proof system in a finite field that's very convenient for them that has all the right properties and then they try to simulate the mathematics of P256 in their field and that involves a 100x blow up in the complexity. Um, one of the things we've done in our paper that, you know, Matteo's been really critical in figuring out is how to build a efficient uh method for read Solomon encoding with the P256 curve. That's one of the things. Um, so that that's one of the problems of legacy dealing with

something that was unforeseen like ECDSA was invented in 1991 without you know ZK was actually invented to get around a patent that someone else had. uh and you know so we're stuck with it but because of that it doesn't have a clean security proof it has this weird one uh but it hasn't been broken uh and you know so it's it's a bunch of compromises and one of them is that P256 doesn't have the right structure but we can work around it another one is that you have to use SHA 256 which I know Nico you're going to get to basically giving ZK proofs about SHA 256 is notoriously hard other people have skipped it or you know gone to something like Poseidon we can't do that because that's not what the spec is. So, we have to basically bite the

bullet and figure out how to do it. And we have, I think, um a uh the fastest version. There was a person from the Ethereum Foundation who's been benchmarking uh different uh proof systems on Shaw 256 and uh we gave her our code and we benchmarked it and ours is like a factor of between 10 and 100 faster than the other uh schemes that she's she's looked at. So, cool. Um yeah, we we figured out how to do it and uh do it quickly. Uh again, uh the one of the key insights there uh that Matteo has been critical to work on and we also give um Ben uh Ben Diamond and Jim Posen credit for this is basically identifying a very good finite field to use for shot

256. Yeah, this is great because you're highlighting a lot of the things I wanted to talk about. Reading through the paper, it's full of these interesting insights. You're also highlighting a bunch of people who've been on the show. So, we'll try to dig up some of those episodes, too. We've had Jim on. I think we've had maybe Ben on. I think he's done study groups at least. But anyway, cool. Yeah. And the the things I really wanted to talk about was the proof system itself with this sort of wrapping and this extra masking you have between like one system and the wrapper. Uh, and this we can get to in a bit. There's the arithmetization you were talking about. So, you use circuits over two fields. one is the base field for P 256 with all the entity stuff and one is these binary fields like we have

in binas um and that's something I'm really keen to dig into with you um you've mentioned resolving codes then circuit design as well because you're using hierax and these layered circuits and I was wondering how did you get efficient layered circuits for signature verification message parsing without I guess having a secret that's too deep and that takes too long to prove where would you like to get started. What's your This is the menu. Where would you like to go? Okay. So, Matteo, why don't you talk about the I I would say parsing is a very important idea. Um and so, Matteo, why don't you tell them about how the Seabboard parser works. I think that's a key insight. So, one of the things I've not told you that you

were about about me, but that I also done a little bit of hardware in my life. So, I actually know a little bit of hardware design as well. I'm not necessarily a hardware expert, but I more or less know how that stuff works. So I more or less know how to make circuits of low depth that do various things. Um there is one particular insight that we have in the paper that I think is an idea that should be resurrected which is that you can do parsing at least in certain context you can do parsing through a circuit called a parallel prefix. Uh and the parallel prefix is something that at least in some form has been known since at least the uh the late 50s. I it is well known to all hardware people you know that

they use it all the time but it's not necessarily known to any software programmer or any blockchain expert or anybody. So for example say I want to build a uh low depth circuit that computes the sum of n numbers. So you clearly build a binary tree that takes the sum of even and odd and then whatever you takes the sum of even and odds until you end up with a single element. Um now a more complicated problem is uh well instead of wanting the sum of the entire array I want the output of this circuit to be another array where the i position is the sum of all elements less than i in the original array. Okay so I want all the partial

sums of the array. So this looks like it is an inherently sequential problem right? You you can do it by starting with zero and then keep accumulating and filling the array as you move to to the right. But there is a very simple parallel way of doing it. And this is called a parallel prefix circuit. And this this game has nothing to do with uh um properties of addition. As long as you have any associative operation, you can adop adapt the same pattern to your problem. And this is well-known technology. It is used in all binary otherers uh in in CPUs. If you want to build a 64-bit others, there is probably a parallel prefix circuit inside it that does the propagation of a carry. So the

interesting side here is that you can reduce many parsing problems that you have to pass the the the core format or possibly even jot to kind of an associative operation to which you can apply uh now the parallel prefix pattern and you can build parallel prefix parsing circuits to solve that problem. So you know this is one in some sense innovation in another sense is 50y old technology. So maybe it's not that innovative, but at least it's one technique that we're using. Yeah, it's innovative for the space. I I want to mention that a friend of mine, Bradley Kuzmau, and his wife Dana, maybe almost 30 years ago at this point, maybe a

little bit later, they designed an entire processor according to this pattern. So you the the read it's it's a much more powerful technique than you would think and that turned out to be applicable to our problem as well and very very useful right and in this case you're doing the message parsing in a circuit over binary fields or over the uh6 field we can do it either way okay it depends on the size of the credential like so I tell you one of the other insights we had was uh sometimes we we have this MAC check. So essentially uh checking the signature we kind of have to do in the P256 field because simulating the math I told you takes

like 100x overhead. Um so so we always have to run part of the circuit in P56. Uh and then if the credential is very small maybe we do the SHA and the parsing in the same field the P56 field. Once the credential gets to a large enough size it makes sense to kind of uh make another proof uh in a different field. and for example the binary field for just those components for all the non 256 components. And now the question becomes how can you be certain that this that the prover is using the same instance in both the left and the right circuit. And in our paper we kind of describe a again a pretty old technique for uh checking the consistency of a witness across two different

cryptographic protocols. And that's essentially to compute a MAC a randomized MAC of the witness and then verify that MAC in both circuits which the MAC circuit is can be much smaller uh if the MAC circuit is much smaller than the big thing that you're trying to verify then this uh technique basically has a has a purpose. So that's one technique we use. Just for added context a MAC it's message authentication code. Uh so it's a symmetric keybased uh you know way to make sure that uh a message is authentic or essentially the same in both left and right. And just to you know make something much simpler it's ax plus b. So it's a you know two universal hash function where x is the thing that

you're macking and it's just a * x plus b and a and b are the essentially the key for the mac and we kind of make sure that no single party the proverifier control that king that key. we kind of just do a coin flipping to pick that key. But so let me add just one more u comment to what Matteo was saying like so Matteo's uh this parallel prefix is I think a brilliant idea for parsing the seabore and just to be clear uh the constraints there you can always take a circuit and flatten it to depth one Nico to what you were saying and like for example shinasi and other people spartan other schemes do that they basically take any uh circuit that you want and basically you know squash it down to

level one and now you just verify the level one circuit that unfortunately has a problem in which it creates a lot of witnesses that you have to use in your ZK circuit and witnesses are things that you have to commit to and commitments naturally take this n login uh overhead because you have to use some sort of resolment encoding under the schemes that we're thinking about one of the benefits of this parallel prefix algorithm and essentially our entire circuit design approach uh we exploit the idea that um you know this sum based IP uh does really well It's linear time and it does not require you to commit to intermediate values. So we try to design circuits that are like roughly between you know depth 6 and 16 in order to

reduce the size of the commitment and that's a major factor for our performance. Like whereas other circuits have to you know commit to millions or you know tens of millions of witnesses to handle cir uh problems like ours we end up our circuit we end up committing to something like 80,000 and that's one of the reasons why our scheme is uh is like you know 10 to 100 times more performant and maybe to make it a little bit more explicitly uh I think our major thesis is that some check plus anything is better than anything.

I feel like Justin Sailor would like this. Yeah. Well, Justin and I were on that Hierrex paper. We we share the same exact approach. He's taken this to this jolt idea, but I think the exactly what Matteo said that sum check of anything is better than anything. And we explicitly, you know, apply that to Lao like uh we use La Hero to essentially verify our sum transcript. Interesting. And that tends to be faster than just using Lehero for the original circuit because we've done a bunch of benchmarks for that. So actually this is a great time to talk about the proof system itself. You already described it a bit.

So we said there are two components. Sum check plus anything is better than just anything alone. Uh so in this case sum check can you describe a bit what's happening there and and why we've been talking about circuits with depth for the past 10 minutes I guess. So there there are two general ways I think to to attack the problem. One is to use a commitment scheme and the commitment scheme will uh be able to s to verify simple operations uh um over a set of committed values and the problem of a commitment scheme is that it tends to be on the slow side. On the other hand, we have another protocol called some check which if you look at it can reduce a certain set of claims to a bunch of wires on a bunch of wires to

a uh another set of claims on a different set of wires. So from that perspective some check is not self-contained in the sense that it can only reduce one proof to another proof. On the other hand it also does that reduction really quickly. So the whole idea here is let's use a circuit that has some depth you know not necessarily too large because otherwise we have to run some check for too long but we we have a certain num a certain gates that whose operation depends upon the the values of other gates and we use some check to reduce the claim on the output of of those gates to another claim on the input of those gates. And you do it a few times until you end up on on a claim on the input wires that you

actually have to do necessarily through the commitment scheme. And the whole claim that the whole property that we are exploiting is that there are many fewer input wires than the intermediate wires of a circuit because the circuit is computing something complicated like SH 256. So the whole idea is we use some check to reduce uh many many claims very quickly to uh a smaller number of claims on fewer wires. So visually if I imagine my circuit has a bunch of gates. I have the inputs as the beginning layer and the output is the end layer and we can move through layers and every layer is a sum check. You have to do it backwards.

You have to start from the output. Yeah. From the output. You have to start from the output. Yes. and and move towards the input because you reduce the claim on the output to the claim on on the input but yet but that's the general idea and so this is why low depth because we want to reduce the number of some checks that we are making yes so then we have this this wrapping layer right like so in the paper you talk about encrypting the transcript from all these checks and then wrapping this in the hero can you tell us a bit more about it yeah so the other problem with some check is that it is not inherently zero knowledge so there are ways to make it zero knowledge but they are complicated and instead of making some check zero knowledge we kind of apply

yet another level of recursion. So we are saying well uh instead of sending you the output that the proof produced by some check uh we actually translate the check verifier into a set of constraints for laoero and we use a zero knowledge properties of laerero to hide what the actual proof of some check was. Okay. And that is done by adding a bunch of random numbers to all the field elements produced by some check. And now uh Lero itself can uh can verify that the check proof is in fact correct. So there are really two levels of proving here. One is there is some check proof.

Uh we encode a check verifier into Laerero constraints and then laero produces the proof that it has executed a verifier for some check correctly. you know, just to make it even more complicated. But that's the general I mean, it's something we're used to see, right? A lot of the systems we see in the blockchain world is sort of a hashbased proof that then gets wrapped into a gross 16 sort of zk. Yes. Proof. But I I would say that that recipe is much older. So, one of my favorite papers is this uh everything provable is provable in ZK. Mhm. Uh that's a paper from 1988 and it outlines essentially this recipe which is that you take any interactive protocol you have for some statement. You commit to it and so we commit to it by essentially encrypting

it or exoring it with the pad. So you commit to it and then you basically give a zero knowledge proof that the transcript committed in the commitment I just gave you uh would have verified under the interactive protocols verifier. Uh so if that makes sense that's a kind of a cleaner way to think about the recursion that like we're using larowero to prove that the sum check transcript that we commit to verifies the claims that the circuit uh on input x uh produces output zero let's say. So in this case what do you mean by commit to the transcript? Do you mean sort of our usual commit to every message and do our fatimir or is this a different kind of commitment to the transcript? uh for specific technical reasons, the commitment is basically a

one-time pad encryption. And so because we want this two- round protocol and because we want to use fiat shamir, uh the way we actually orchestrated is at the very beginning the prover commits to a one-time pad. So they the very first message of our protocol is you send a lero commitment to the input of the circuit as well as essentially this uh one-time pad that you randomly pick. Uh you have to send that commitment um and then uh essentially the proven verifier engage in a sum check protocol for the original circuit and instead of me sending you the sum check message I essentially send you uh the message exord with the pad that I've committed.

So you essentially end up with a one-time pad encrypted transcript of the sum check and then we finally finish with a laera proof that that one-time pad encrypted transcript would have verified. Now we can take that entire thing which is interactive in many rounds. We can use fiat shamir because every message of that was a public coin message. Uh so we can use fiat shamir. I I hope that kind of explains why we orchestrate and why we use that commitment scheme. And so to be clear, we only apply fetchamir sort of to the the whole composed protocol, not to the inner part and then wrap again with something that's been fetchir. Exactly.

Because otherwise you'd have to make proofs about fatimir uh queries which we don't we don't think is a reasonable you know if you don't need to do that we don't want to do that. Yeah. The security guarantees there are very different right. Okay. So that's super interesting. And now this takes us to sort of the last thing I had on my little menu earlier, which is all these proofs require efficient operations, things like FFTs or entities, I guess some people like to call them. Uh, and we've been using these fields that don't naturally have FFTs, right? The field of P 256 and the binary field. In the case of the binary fields, we have an inkling of how that works, right? Because Bignyas and that type of work has told us about additive FFTs. Uh but how did

you do it for the ar the curve and how did you do it for your specific binary field? Oh well it's actually fairly simple. Uh so the P256 field does not have the proper root of unity that are usable that they don't you cannot do an FFT of size 2 to the K which is what you really would like to do. However, the quadratic extension of a field does quadratic extension is uh you know the in this case it has a form of a complex uh so you you can pretend that a quadratic extension is an element of a base field plus square root of minus1 times another element of a base field.

So it looks like the complex field. You know this is not a general property of all fields but it is true of this one. And it happens to have a a root of unity. And it's actually kind of funny because when we figured this out, we thought it was kind of a cosmic coincidence that the quadratic extension happens to have exactly the thing that we need. But thinking more about it, when cryptographers pick prime numbers to use, they're usually some, you know, big power of some number times some big power of two plus or minus one. Yeah.

Okay. And they use that so that the arithmetic on a normal processor, the multi-precision arithmetic on a normal processor is easier to do because you you're multiplying by a large power of two. So there is usually no work to be done and you know they happen to have picked the uh minus one case which doesn't quite work for us. Uh however if that's the case then the the quadratic extension always has the plus one which now has the right power of two uh number of roots. So this is not a cosmic coincidence. I I have a meta theorem in my head that any prime number picked by cryptographers will support an efficient FFT. You just have to know which case you're in. So this is very interesting because uh something similar is happening in this paper called circle

stark. I don't know if you're familiar with it. Yes. And the idea was to run Okay, great. How how does that compare? Well, so we have something to say about that. We've been in contact with Oric and I think we have a much simpler explanation of what's going on in circle FFT. Uh so we're going to write a very short paper on that uh shortly. So we don't want to say too much about that but uh amazing looking forward to it. Let me just uh point out one more thing which Matteo is a little bit uh um humble about but he's also figured out so there's a birectional FFT. That's kind of a new idea that we've added. Uh and that's something we also we do in the binary field. So um Diamond and Posen you know brought to our attention

the LCH14 um additive FFT algorithm. Uh but like the I think our contribution there is this use of this birectional FFT in the case of read Solomon encoding and we can we can apply that everywhere actually um for all the read Solomon encoding things. gets a constant factor improvement which is of course important when you're trying to run a proof on a phone. Yeah. The the specific problem of all these FFTbased methods is that your input array has to be of a size of a power of two which isn't necessarily convenient for LA hair or if you're trying to integrate with something else that has different constraints. So the problem is how do you do the FFT for non power of two things and specifically how do you do read Solomon encoding. So there is this birectional FFT thing that

we have in the paper that uh kind of solves the general case for arbitrary sizes in a very simple way that you can study. What do we mean by birectional? Birectional means uh uh I'm doing it. So in the normal FFT either I give you all the inputs and you give me all the outputs or you can run it backwards and you can say I give you all the outputs and I want all the inputs. There is a way to say well I know that all the input that you know k of the input coefficients are certain numbers that I know and n minus k of the outputs are a bunch of other numbers that I know usually zero now give me uh whatever remains uh so that that's an important problem for doing interpolation if you

if you are interpolating a polomial of degree five right and you have an fft of size eight you don't know the other three coefficients And uh so either you pad everything to eight and blow up the degree which makes everything else run slower or you just stay with five and this birection will give you the rest. It's kind of cool actually. It's it's a very intriguing idea. So we we get away with not having to pad to the nearest power of two and still being able to run ours. That's amazing. H I wonder this might have already been answered in what you were saying but you know you're talking about circuits over a b a primary field and also over a binary field and I'm just wondering is there

any connection between those two things like are are they talking to each other? Yes, they have to for soundness uh otherwise a prover could basically say something to the P256 field and then say something totally different uh and you know make convince the binary field. So that's where I was telling talking about that MAC. Uh one of the things we do, we augment each circuit in each field with a small circuit which computes a MAC. Um for all the common inputs to both circuits, we ensure that they're equal, that they're same inputs we're using. So for example, the signature that we're checking is uh in the P256 thing, it corresponds to the same message that we're computing the hash of in the uh binary field. Okay, that's the

connection point. Then Mhm. you don't have any you don't have like a new proof or anything to link them. It's just by using the same or would you call that a proof? Well, we have a security analysis of like a written security analysis, but there's no auxiliary proof. Uh it's it's it's just um two proofs in these two circuits with this uh joint input. Cool. Just circling back to the FFT, there's one last thing I wanted to ask is you've said we have to work in this uh quadratic extension. Does this mean that I have sort of a two 2x blow up every time I'm going to run the FFT? Uh so that's uh that's what we're going to write about uh oh okay in in this no no but this is actually a simple answer to

this uh the answer is no because uh so let let's stay on the analogy of real numbers versus complex. Let's forget about the the the finite field for a second. So you can compute uh uh an FFT of real inputs in about half the number of operations of the equivalent FFTs of the same number of complex inputs. Okay, so there are well-known algorithms that have been studied forever uh by which you can uh um you can save half the operations. It's actually interesting because in what we talked about in the paper, we didn't even bother to do this.

It's a little bit more complicated and we just wanted to have something that works. we have actually implemented the thing more recently and saved it saved a few milliseconds from the whole system. Uh but you know this is well known technology it's uh that has been used forever for for 50 years 60 years. So then maybe I've misked my question. I was trying to nudge you towards another part of the paper where you talk about sort of new readment codes where rather than picking roots of unity and using those as our our domain for solment encoding you picked something different and there were some nice properties there. So there is a definitional problem here because even though you can compute the FFT in approximately the same time over the extension field that you could in the um original field uh

it's still a polomial evaluated over roots of unity in the extension field and we didn't like that. We didn't like the fact that in order to define what LARO does in its own based field, we have to come up with a complicated concept built upon in the extension field and we also didn't like the fact that root of unity really depends on the field. And so we are now if if we are trying to standardize and define what an algorithm that works in all cases, we we we need this root of unity that may or may not exist. So we came up with this uh um way to do interpolation over integers you know over 0 1 2 3 and you know small integers which if you look closely at it it is just Newton

interpolation expressed in a clever way uh and reduced to a convolution but it's a it's it's kind of a known technique that was never made explicit anywhere as far as I can tell so we wrote it down and that's what we're doing. I love how you told us, oh, it's just uh all these things that we have not heard about, but don't worry about it. It's very simple. You did mention standards actually, and this is a good time maybe to to get out of this technical deep dive and ask you about libk, which is sort of a library, I guess, that comes out of this project and also an ITF draft. Could you tell us more? Yeah, so we have a GitHub repo that we're going to make open source. Right now it's in a

private preview. Uh so we've like shared it with a bunch of technical uh you know collaborators um you know experts like Mutu and other people to get their feedback on it. We're going to make it fully open source uh later this year. And we've also we spent a lot of time writing a very formal spec for our whole system. Um we spent a lot of time making sure that someone could read that and basically replicate our system. Um and we've posted that on IETF. Uh but the the standards process are kind of slow. Um always are. The ISO has basically adopted part of uh our approach. Uh they're adding messages to their MDOC

standard that will basically support CK proofs. Um but yeah, we're looking for more help in getting these things standardized. these are actually going to be deployed and so we'd like to get uh but you know takes a lot of effort to get consensus in the community. Yes, keep in mind that our target is government organizations like you know the European Union issuing passports and so they need some kind of reference document uh and so we we are focusing on standardization specifically for this reason to to make it acceptable to governments. Cool.

I want to ask something kind of going back to the product and the the wallet. Um what happens? So this is actually something that I think is like a very real life case, a bit of an edge case, but in this story that we've heard so far, you know, we create this credential, it's now in the wallet and then you can use it. What happens if you have to like revoke it if your passport was to get stolen? And the reason I I mean the reason it's maybe good to ask now is there are other works there's other kinds of like CK systems which slightly try to address that and I don't know if it's already addressed or if it's something that you're planning on addressing but yeah do you know what to do if if you actually have to revoke it already you ask all the hard questions

excellent so uh revocation is something we've thought a lot about we've uh explored all of the accumulator based schemes and a lot of the uh legacy based approaches We have a a different approach to it that we're also pushing through to standardization. Basically, the the features of that are that you only need a constant size witness and the amount of work that the revoker has to do is kind of proportional to the number of revoked credentials, not the number of issued credentials. But so we do have a solution to that. If you're interested in the details, I can give you some some high level. But the point the high level point is yes revocation is a nasty problem that many cryptographers overlook but that

practitioners demand a good solution to um the first solution to that is just to ignore it by saying well the issuer can just you know re renew their issuing every week or so like and so you know to to revoke it is essentially you know it it automatically revokes at the end of the week let's say and and you just get a new one. So, just to be clear, this would mean every week the state of Massachusetts gets a new public key. Like, not a No, no, no. The state of Massachusetts doesn't need a new public key. It's just that every week essentially the state of Massachusetts signs a new credential for you and sends it back to your phone. Uh unless, for example, if you report your phone stolen, then it'll basically not issue that device public. It won't give a

signature on that old one. Um so, that would be the simplest way. However, um many people have asked for revocation where as you said, if I if I lose my document, I should be able to revoke it within the hour. And with for for that kind of system, uh you have to take into a number of considerations like how much work does the phone have to do? How much information does the phone have to download? How much work does the revoking institute have to do? How much work does the relying party have to do to verify? And so balancing all four of those things, we kind of have a good solution. We've spoken about it at um many of these conferences like uh these identity conferences. We got gotten a bunch of feedback on it. But this would be built into like the architecture I it

sounds like of the larger system. It's not built into the cryptography per se, is it? Right. So essentially we update our circuit. The circuit we use to verify the claim. We add a claim that basically says and this credential has not been revoked. And the way we implement that is of course in this like you know we have a specific way to implement that but we just modify the ZK proof and then of course that requires all the other parties those other three parties I mentioned to do things and to publish things and uh if they all agree and I think one of the benefits is to make it so that even if one of them doesn't really agree you can kind of gracefully uh degrade to a system that still works. Cool. I have one last question that is a little bit off topic.

It's you you've actually mentioned this earlier in the episode, but I wanted to ask you about working around patents of certain cryptographic processes or yeah, types of cryptography. The reason I bring this up is actually in a bit of research for this episode, Abby, I saw your talk on I think it was just on ECDSA and actually you've mentioned this. So there's there's a patent that has blocked people from being able to create this system in a more simple way and so there's been these workarounds. I wanted to talk to you a little bit about what you've seen over in the years that you've been working in this space with patents. Do you see value in them? Do you see them mostly as a hindrance to like the larger field? Yeah, I'm really curious to get your thoughts. Okay. Uh

well, I think patents have their place uh in cryptography. I think it's very hard to work with patents. um we have this experience with ECDSA where I think the simpler scheme was patented and thus couldn't be used and I think the world would have been easier place with uh the simpler schnorebased signatures. There was the example of the RSA patent which did expire and then that like after that became much much easier to use RSA as an algorithm. Um so I personally have like uh I don't have much experience with the value of patents and like you know whether the argument that it fosters innovation is true or not. Yeah. But in crypto, I think it's better not to have patents and to have um like open schemes and have the world pick simpler uh more

performance schemes. Yeah. And maybe just to explain a little bit like what does a patent do? You sort of say this like there was a patent and therefore the scheme couldn't use that technique. But I mean, I guess the reasoning here is because you need something where you won't have to be paying like a license fee, a company every time you use it if you want to be using it as a standard, right? That's right. Most standard bodies do not adopt schemes that have that are encumbered by patents because they're afraid that if everybody adopts it and then the patent holder decides to change their stance on the licensing, then everybody would be forced to essentially um pay rent. uh you know there's like a rentseeking behavior

you're trying to avoid there. Yeah. I think in ZK we've been at least in the last 20 years or so 15 years we've been kind of lucky where there haven't been like hardcore patent teams and teams have built amazing software where they they've invented techniques where I think they could have and they didn't and it allowed it to be free. Yeah. So just to be clear like when people have asked inside whether we want to patent these things we've been very clear that we don't want to patent this and we want to make it open source. We want to make it easily adoptable by anybody. Well, thank you so much for coming on the show and sharing with us, you know, your work on the Google Wallet, the ZK system that underlies it, all of the kind of amazing breakthroughs and research that you've done to be able to

make this function the way you need it to. It's been really cool. Thanks. Thank you so much, Anna, Nico, for inviting us. Of course, we love talking about our work and thank you for the excellent questions that you asked. Very deep and very insightful. Dave, thank you. This was a lot of fun. Yeah, we don't normally do these kind of things, but this was we had a blast. Cool. Yeah, thank you both. Yeah, this was for me such a pleasure to read through the paper and like I've been saying, it's full of these incredible insights. So, thanks so much for telling us more about it and allowing me to pester you with all these questions. It's great questions. Great questions. All right. I want to say thank you to the podcast team, Rachel, Henrik, Tanya, and Kai, and to our listeners. Thanks for listening.