# ZKPs and "Programmable Cryptography" by gubsheep | Devcon Bogotá

- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2023-10-07
- Duration: 31:57
- Watch: https://streameth.org/watch/yt-qAfprVCBhdQ
- YouTube: https://www.youtube.com/watch?v=qAfprVCBhdQ

## Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.
https://archive.devcon.org/archive/watch/6/zkps-and-programmable-cryptography/

Historically, cryptographic protocols have been built special-purpose for specific kinds of claims or information hiding mechanisms. zkSNARKs and other new cryptographic tools move us to a world of "general-purpose" cryptography, where we have expressive languages to express claims about digital identity, reputation, and more. We discuss a high-level framework for thinking about where and why ZK and related technologies might (or might not) be useful for digital applications.

Speaker(s): gubsheep
Skill level: Intermediate
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: ZK,Zero Knowledge,Programmable Cryptography

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

foreign [Music] I'm gupsheep and I work with the research focused organization called Xerox park today I will be talking about this idea of zkp's and programmable cryptography which is a phrase that we use to describe a lot of what we focused on at Xerox Park I'll describe what programmable cryptography means and why we think it's important for anyone who is interested in the future of Next Generation blockchain and decentralized applications so first off I'll give a little bit of context into what Xerox Park is for folks who have not heard about this organization Xerox Park is a relatively new research focused org which supports what we call application Level r d on ethereum and other decentralized platforms so this means trying to better understand what is possible to do on these kinds of you know smart contract platforms or with new decentralized application technologies that isn't necessarily currently possible today but might be on the horizon um projects that we support include things like Dark Forest as well as Persona Labs building things like hanging on or if folks were around the applied ZK showcase yesterday you might have seen proof of email or various ZK machine learning experiments we also uh build circuit Primitives for ZK snarks and focus a lot on infrastructure maintenance and third-party development of tool Stacks like snark.js sir com Halo 2 and more and we also do a lot of community building efforts and we work on Cross team and ecosystem-wide projects as well cool so one of our largest areas of focus at Xerox Park is applied ZK cryptography um which means that a big Focus for us is understanding what is possible to do with DK crypto what you know theoretically should be possible to do with DK crypto and decentralized apps and what we need to do to to get there to eventually bring those kinds of tools to production and apply ZK is one of a category of relatively newer cryptographic Primitives that we categorized under this term programmable cryptography um and in order to describe or you know give a feeling for why uh programmable cryptography is important first I want to go into a little bit about the a couple of the reasons that we think that applied ZK is especially as uh important so um there's two concrete reasons that I think are especially compelling in terms of why ZK is going to be powerful for unlocking the next generation of decentralized applications um and I'll just go through those real quick so the first thing is that zero knowledge cryptography gives us what I think of as an expressive language for claims so what does that mean we'll go through an example to to get a sense for what an expressive language for claims looks like let's take the example of um ZK snarks and group membership proofs in the context of claims about digital identity so um the uh simplest kind of identity claim that we have from cryptography and something that we've known how to do for many decades is prove a statement like I know a private key corresponding to um someone say like Alice's public key which implicitly identifies me as Alice so this is something that I can do with a digital signature something like you know RSA or ecdsa the invention of public key cryptography made uh proof like this possible or made provable statements like this possible and this is infrastructure that underlies so many of the digital systems that we know and rely on today including you know secure traffic on the internet as well as blockchain systems like ethereum or Bitcoin so going up one level uh in complexity from the previous slide we have claims like I know a private key corresponding to one of the public keys in a group so for example I know a private key corresponding to one of Alice Bob or Charlie's public keys this kind of claim is commonly referred to in the literature as a group signature or a ring signature we do have cryptographic protocols that are purpose built to enable people to generate you know group signatures or ring signatures but they are again special purpose built for this kind of claim and the math or like the cryptographic protocols that make these sorts of claims possible are oftentimes incompatible with the math used for ordinary signature schemes so you know we figured out how to do these group signature schemes a few years after we figured out how to do digital signatures in general however it is the case that in order to make claims like these or in order to build up a system or a network in which people can make these claims you have to build uh you have to bootstrap like an entirely new um you know key registry you have to build a different uh key generation algorithm and you have to popularize that so you know the math involved in making a claim like this can be can be incompatible and require you to sort of move to an entirely different system than if you want to uh you know uh use systems that allow you to make claims like this so one thing that I want to note is that today um however we have uh another much easier way of uh enabling these kinds of claims and a manner which a way which is you know actually compatible with systems for proving the first kind of claim so with DK snarks the problem of building a system that allows you to make these kinds of claims from A system that allows you to make these kinds of claims is actually a really simple essentially two-line code change in a ZK circuit so rather than having to invent an entirely new mathematical protocol or new key generation algorithm if I have a primitive that allows me to prove in a ZK circuit that I possess a public key corresponding to some private secret then what I can do is I can construct a ZK circuit that says I know some public key corresponding to some secret private key um I'm going to keep that public key Secret and uh that public key minus hash one times public key minus hash two times that public key minus hash three equals zero so if I can prove all of this in zero knowledge what I'm effectively proving is that I know a private key corresponding to one of these three you know public commitments hash one hash two or hash three so um this way I now have this system which uses the exact same key generation algorithm or key generation strategy as a system that allows me to you know simply prove that I know the private key corresponding to Alice's public key and we've turned essentially this problem of Building Group signatures from a math problem where we have to go to a cryptographer they have to write us a paper I'll do all this stuff bootstrap a new key registry into essentially a programming task that um you know any developer familiar would say Circle can carry out okay so slightly more complicated than this we can go a level even further up and consider augmentations to this protocol such as I know a private key corresponding to one of Alice bobbert Charlie's public keys and the other two either can or cannot prove that they did not generate this message so sometimes this is this property is called by various different names um some call it like disavowel so as an example like suppose I'm Bob and I generate a signature that is uh either coming from uh you know you can see is coming from one of Alice Bob or Charlie um Alice or Charlie might be able to generate a proof that uh they did not create that signature so um yeah there's cryptographic systems that allow you to toggle this property on or off uh but again these use new math are incompatible with previous systems and are generally fairly difficult to engineer again however with the DK snarks this is a pretty trivial like two line circuit code change um so again we're sort of seeing this idea of this language that allows us to build these expressive claims that are compatible with uh you know previous claims that other cryptographic systems will allow us to generate and finally we can get to claims you know of this level of complexity something like I know a private key corresponding to one of Alice Bob or Charlie's public keys and I either possess a signed attestation from one of David Eve or Fred one of these trusted you know attestation service providers or during a block with header X I knew the private key corresponding to an account with at least 32 eth and you know dot dot you can kind of compose a bunch of arbitrary uh you know predicates on this identity claim and I think it's pretty fair to say that there's like no cryptographer in the world who you could go to and ask them to build a special purpose new cryptographic tool that would allow you to prove this specific kind of claim nor would it even make sense to but again with DK snarks this actually becomes fairly trivial you have your building blocks in ZK circuits for each of these things you know uh key pre-image signature recovery um proof of inclusion in the ethereum Merkel Patricia try and then you can just put all these together essentially calling all these like different functions in your ZK circuit code to start building out these claims so another framing of this idea of the expressive language for claims is that ZK snarks turn math problems into programming tasks rather than having to go to a cryptographer to write you a new paper every single time you want a new kind of digital identity claim to exist in the world and be provable you can just have a ZK circuit developer compose the right Primitives inside ZK circuit code okay so cool thing number two which is closely related to cool thing number one is that ZK adds interoperability to cryptographic systems so what does this mean well to explain this first I just want to do a quick breakdown between two terms snark friendly versus snark compatible cryptographic Primitives Stark friendly cryptographic Primitives are um you know Primitives like hashing algorithms or digital signature schemes or encryption algorithms that are specifically purpose built for um to be efficiently provable inside of ZK snark proving systems so for example the Mims here Poseidon hash functions or eddsa signatures um these uh cryptographic Primitives uh oftentimes have been invented in the last couple of years and you know the hope is that with these Primitives we can move towards a world where we can do more and more inside of snarks um however most of the cryptographic systems that exist in the world use cryptography that was invented before we knew about CK snarks so for example a lot of hash functions use a lot of bitwise operations which are very costly to do inside of ZK snarks um and so these these systems are not snark friendly but they are what we have to work with so for example all the signatures on uh you know emails signed by mail servers that are being sent out are not going to be snark friendly um signatures however we can start to at least connect all of these different snark compatible systems together um by embedding these different signature algorithms hash functions encryption teams Etc inside of snarks even if it is costly so as an example of a few crypto systems that exist out in the wild we've got key distribution and identity Registries such as like you know you can build a an identity registry of like gpg keys um GitHub allows you to generate locally a key pair and upload it and make it publicly accessible to anyone so that anyone can verify you know your commit history or things like that repos you've contributed to so for example if you go to github.comeep.keys you'll see like my RSA Keys um ethereum and Bitcoin rely on the ecdsa signature scheme so addresses are going to be you know a hash of an ecbsa public key in ethereum and I think mail servers use the dkim protocol to sign and authenticate messages which under the hood relies on RSA so one of the things that's going on with all these different signature schemes is that they kind of can't really talk to each other you know if you're running on the RSA protocol you can't really understand an ecdsa signature um however by making all of these Primitives snark compatible by implementing RSA signature verification ecdsa signature verification etc etc inside of snarks what we can start to do is we can start to build adapters between all these different systems um so again if I have an RSA primitive and an ecdsa primitive inside of a snark then I can start to make claims like either I have a GitHub account that's contributed to the you know ethereum GitHub org or I possess at least 100 eth and again by making existing cryptography uh snark compatible and combining that with this expressive language for claims we can start to make statements about all sorts of digital or online activity so both of these features are examples of the power of programmable cryptography which probably is you've grok from now um you know both of these features are giving us these tools to much more flexibly manipulate digital objects so now I'm going to kind of give my description of programmable cryptography which is that it is uh cryptography that can be layered on top of arbitrary computations to contrast this with cryptography that we've been using for the last couple of decades well for more most of cryptography's Short History the set of mechanisms that we've been able to instantiate with our tools has been you know quite narrow so we can say things like this message originated with Alice as we've seen or this message can only be read by Bob but every single new mechanism that we want to build whether it's like you know arbitrary identity predicates or read permissions or things like that would require us to build a new special purpose cryptographic system however now we're seeing tools like you know ZK snarks as we've discussed that allow us to move from this message originated from Alice to I know a private key corresponding to one of these people I have an attestation from one of these service providers etc etc um to things like witness encryption uh witness encryption is a primitive that essentially allows you to encrypt data not with like a key pair where someone has to know a certain secret to decrypt the message but it allows you to decrypt messages with or sorry encrypt messages with a program so for example uh I can encrypt a message with a Sudoku puzzle and anyone who solves the Sudoku puzzle will be able to generate a key to decrypt the message that I've encrypted uh with witness encryption and this allows us to move from systems where we can do things like Charlie has published some secret vote that only a coordinator can read with the coordinator's private key to Charlie has committed to some secret vote that only a testers with a certain permission level can decrypt today but which a class of Auditors with a lower permission level can at least partially decrypt in exactly you know one week uh I would say that smart contracts Also spiritually uh kind of fall in the same category as a lot of these other programmable cryptography Primitives so um you know imagine very early on in the history of uh this idea of blockchains uh we would have these consensus engines where people could come to consensus on only very simple or specific data Transformations data Transformations like you know Bob can decrement his balance by 100 ether to increment Alice's balance by 100 ether nowadays with smart contracts and programmable blockchains we can sort of execute arbitrary predicates you know at Block B 100. ether will be available for withdrawal by Bob so long as Bob has closed his position in some smart contract and no one submitted a fraud challenge though an early withdrawal may be initiated if two of the following three solvency conditions are met etc etc so in each of these examples there's this common thing theme of moving from the specific to the general with ZK snarks I can move from proofs of specific claims to a general purpose language of claims smart contracts allow us to move from coming to consensus on canonical data that can be modified in only very specific or narrow ways to a general purpose language for modifying or executing code on this canonical data witness encryption moves us from a world where we can permission data to only be read by a specific person or specific set of people to having a language for specifying arbitrary predicates for read permissions so I kind of imagine this as like you know decentralized oauth tokens where anyone can plug into this like Global authentication system and specify who can read what and when um and there's all these New Primitives that are continually getting better and better and more and more feasible things like fully homomorphic encryption multi-party computation even really far out things like indistinguishability obfuscation uh and more um oh and you know I there's a couple of folks who have sort of independently come up with this categorization or framework I believe this Thursday team calls these computational crypto systems um so you know very similar in general Spirit to what we're calling programmable cryptography okay so um the second part of this basically thesis is that programmable cryptography uh itself seems like a very powerful tool blockchains are also a very powerful a powerful tool but it's not sort of a priori obvious uh like why these two things are related to each other except that they both sort of derive from similar mathematical principles but I claim that there's actually a very deep and complementary uh marriage between these two powerful things and to explain why I think that is first I want to give my kind of mental image of what ethereum as a data availability layer looks like say like five or ten years out from now so in my head the way that I kind of conceptualize the idea of you know ethereum the global data availability layer is I think of ethereum almost as this like you know giant super thick coaxial cable that basically streams Humanities like Global stream of Consciousness um so Humanities you know promises bets Secrets debts dreams etc etc and this coaxial cable is uh you know made available to any person or Computing device in the world so um you know any phone any computer that like lives on some you know like institutional server anything like that can hook into the one gigabyte per second canonical data stream look up data and know that they're seeing exactly the same thing as someone across the world is seeing now right now this data stream is completely transparent and that has been a design decision that has been necessary in order to gain acceptance of this particular data stream that we're wanting to claim is the canonical data stream or the legitimate data stream so in order to build acceptance we have this principle of don't trust verify and in order to verify you need to be able to see all of the data but I claim that this is actually extremely limiting there is a wide class of applications that you might care about to build where you don't want every piece of data to be completely public and I think that when a lot of people talk about this idea of privacy or information asymmetry you know people have various different beliefs on uh like various ideological nuances around privacy but I want to go even a level lower to explain why I think this is important privacy is important not just as a matter of ideology but simply as a matter of mechanics there's certain coordination systems that just don't work unless you have information asymmetry and in fact most of the complex systems that we see in the world today and most of the organizations we have in the world rely on the idea that different people know different stuff and can do different stuff so the way that I think about this is that what we would really like to do is we'd like to be able to enforce read write execute permissions on this canonical data stream that is uh the blockchain and the way that we do this is you know in fact programmable cryptography programmable cryptography gives us these expressive tools and languages for enforcing read permissions like we mentioned with things like witness encryption or write or execute permissions which we're seeing with things like you know ZK snarks and smart contracts and more so to give just the toy example of uh why this kind of permissioning or access control is really important I want to consider the example of games so for example let's uh let's consider poker in poker a lot of the depth of the game relies on the fact that I know my cards but I don't know your cards and you know your cards but you don't know my cards poker as a game would simply not work if we knew each other's cards it would be completely degenerate right like it wouldn't really make sense it wouldn't be any fun um and uh you know a slightly more complex example of this might be uh strategy game so a couple of days ago we had a talk on Dark Forest which is a fully on on chain strategy game you can kind of imagine it as something like Starcraft on the blockchain and one really key mechanic of Dark Forest is that in Dark Forest um players respective locations are all hidden which gave which gives the game a lot of its um you know relative strategic depth so the general pattern here with games is that uh oftentimes what we're going to do is we're going to have players commit to a state that they keep private and whenever they want to make a state transition they're going to provide a zero knowledge proof that they are making a valid update on uh their private State and committing you know a valid State commitment to the network so this proof might prove something like I'm moving my you know secret night from secret location a to secret location B I'm not going to tell you what a or b are but this zero knowledge proof proves that you know there's an L shape between them um or zero knowledge proof might prove something like drawing some card I'm drawing it validly according to the rules I'm drawing it out of a randomly shuffled deck I'm not cheating and just like continually drawing a bunch of aces so you know there's a bunch of uh game examples which we can kind of Imagine where the game just simply does not work if all of the information is transparent and while those are kind of toy examples I think they allow us to start to hint at this more complex future where we're using blockchains for a much wider range of use cases so you know I think one completely digital uh completely reasonable digital interaction we might expect to see something like in the future is you know imagine like I walk into a store and perform a cryptographic handshake with the merchant and perform like a multi-party computation with some identity provider after verifying the Merchant's identity I give the merchant one token that permissions them to access some specific data uh on my preferences for an hour and another token that allows them to transfer a limited amount from my balance after that transaction completes I update my transaction history that's private to me and committed on chain uh but only visible to myself so you know each of the components of this interaction today are not possible due to the fact that there's so many things there's so many constraints on what we can keep private but again with things like fully homomorphic encryption witness encryption ZK snarks etc etc these kinds of interactions may start to be unlocked uh while still preserving the neutrality uh where all this data is living on some like globally verifiable blockchain or data availability system so um the last kind of like analogy that I want to make here to kind of create an image of what this future might look like is you know I want to kind of uh describe the concept of an Ender Chest from the game Minecraft so Minecraft is a you know Sandbox game in which you can Harvest resources and build stuff and in Minecraft there's this concept of chests so with a wooden chest if I build a wooden chest I can like place it down here I can put items in into the chest if I leave and come back the items are still going to be there the chest is a very important like primitive in Minecraft if anyone else goes to the chest and they open it they're going to be able to see all the items that I've placed in there um in Minecraft there's also a very powerful uh tool called the Ender Chest which is sort of similar to a chest but has these kind of this kind of magical property where ender chests inventories are marked as like per player inventories and are sort of shared across every Ender Chest that exists in the world so if I put an ender chest down here and put down like you know five stone or something and then I put an under chest down over there and like I walk over there and open it I'm gonna see that same five Stone um and if someone else walks into the uh walks over to the under chest they're not going to see that same inventory that I have they're only going to see um you know what they've put into the under chest the ender chest is an incredibly powerful tool for Minecraft players that allows them to execute on these larger scale strategies build these much more complex constructions it just makes it easier for you to do a lot of things and I think as more of our social and economic activities Move online we're going to need Primitives like these these digital ender chests that allow us to carry things like our reputation our financial history our social context across different platforms and in order to do that we're going to need these new privacy preserving mechanisms uh that fall under this category of programmable cryptography so that's all I've got for today if you're interested in any of the work that we're currently working on around programmable cryptography or anything else you can check us out at xeroxpark.org or you can find us on Twitter at Xerox Park but thank you and thank you for the talk um as we went through a lot of the slides there were examples of ZK things where you have a claim and it's true or false and you prove it but I guess the bigger picture of all programmable cryptography could have other sorts of statements like I summed all these numbers and this is the true sum and so I guess those are other flavors and maybe that's homomorphic encryption I'm not sure how friendly are those with each other right now like proving things and doing math and getting continuous results yeah this is a great question so um right now you know as you've probably noticed like we are specifically very focused on zero knowledge cryptography which is you know one of one piece of this like much broader category but it seems like disproportionately represented um so why is that the case well uh one reason is that zero knowledge crypto systems are simply much more mature today than a lot of these other systems where there's there only exists theoretical constructions or academic implementations um we expect things like witness encryption for example to be much further out and we're still even trying to like describe the landscape of what is possible to do with multi-party computation um so unfortunately none of these systems are super compatible because a lot of them don't yet like exist in a form where you can meaningfully start playing around with them but we hope that that is going to be evolving rapidly over the next say like you know a couple of years hello thank you very much by the your talk haven't made any kind of research around Quantum cryptography ZK yeah so um I think Quantum cryptography is a slightly like orthogonal direction to what a lot of these tools um are going to enable uh specifically for example like one way that we think about the interaction of quantum cryptography with these tools is considering which of these tools Quantum or like which you know for example ZK algorithms uh or like fhe algorithms we have are quantum resistance in other words once we have quantum computers uh which of these algorithms might we be able to break now that's kind of a different thing however from necessarily um you know the affordances of these tools so for example like um you know it's when I think about programmable cryptography I usually think about it from the perspective of like what these things can do for us rather than necessarily like what's the underlying algorithms and what are the computational models in which they might you know broken by or enabled by whether that's Quantum or elliptic curves or you know large Prime fields or things like that oh thank you for talk can ask you if I understand it correctly the state currently in Dark Forest uh you keep it locally and you just put the proofs on chain um that may not be ideal for the future if you lose the state you kind of lose the game uh like what are your thoughts on how to keep the state safe in in other ways either using a homo marketing prescription or your general thoughts around it yeah this is a great question and I think like you know as an extension of the debate that people have around the viability of uh you know everyone custodying their own keys for example on a blockchain um I think that there are uh a couple of things here that might be possible one is like you mentioned and fully homomorphic encryption might allow us to store private State on that is encrypted on you know cloud services but still be able to like retrieve that data and perform operations on it just like we would if it was local while still preserving the privacy of that data that's pretty far out though and in the meantime I think the most immediate thing that we can focus on doing is like building more user-friendly solutions that allow you to keep critical or sensitive data on your own machine I mean everybody already does keep critical and sensitive data so it's a question of like as the volume of that data or has the sensitivity of that data grows then how can we make those systems even more and more ergonomic and more and more secure all right thanks for the talk um what do you think about the fundamental bottleneck of like zkp's being quite slow and you have this trade-off between like proof generation and verification do you think we will have sort of more like external offram Solutions maybe like layer 2 is for full ZK or like do you see the most promising Solutions being in like fundamentals ekp research like what do you think of that whole opponent trade-off yeah so personally um I think that there's still a ton of low-hanging fruit uh in terms of performance optimization for these currently very expensive crypto systems um for example with ZK by some metrics over the last three years the or like over the last four years the size of circuit or like the size of computation that you can ZK prove in browser efficiently uh has you know expanded by like three orders of magnitude and we're still seeing like rapid improvements via new protocols new better engineered libraries for proving Stacks more efficient circuit implementations and things like you know ZK friendly Hardware are just getting started so I think that like well eventually uh there may be some industry of services that arises around you know offloading computation or things like that at the moment there are still a lot of optimizations that have not yet been fully you know explored um that I think can enable some really really complex proofs even on like small client devices like mobile phones is there any other questions cool thank you