Programmable Cryptography

Transcript

hey everyone my name is Brian goo and I am the executive director at Xerox Park thanks so much to the edcon team for having us here today uh the topic of my talk today is this idea of what we call programmable cryptography its relation to zero knowledge cryptocity and how we think about this in terms of implications for uh the future of ethereum and blockchains broadly so first off just to give a quick intro Xerox Park is a relatively new research focused organization which supports what we call application Level r d on

ethereum and other decentralized platforms so projects that we either operate or support include things like Dark Forest we build a lot of circuit Primitives for ZK snarks we work on a lot of infrastructure and maintenance of or third-party development on top of tool Stacks such as snark circum Halo 2 and we do a lot of community building work as well um so as I mentioned uh you know one of our most major areas of focus at Xerox Park is applied zero knowledge cryptography which means understanding what is possible to do with uh zero knowledge crypto to enable the next generation of

ethereum decentralized apps and what we need to do to get there so um we're going to be talking about applied ZK in the context of this larger idea of programmable cryptography and first what I want to do to motivate that is I want to explain a little bit uh on why it is that we are so interested in applied ZK what are some concrete reasons why we think that applied ZK is something that's going to be really powerful for unlocking the next generation of these kinds of decentralized applications so first off I want to talk about two things that ZK allows us to do that are I think huge leaps forward over what was previously

possible so cool thing number one is that ZK gives us what I call an expressive language for claims and rather than defining that outright I want to sort of illustrate it with a handful of examples around identity claims and membership proofs so one of the simplest kinds of statements that we can make with cryptography is statements like I know a private key corresponding to Alice's public key this is something that we've known how to do for many decades at this point um you know the invention of public key cryptography enabled us to make statements like this um and yeah it's something that underlies a lot of the digital systems

that we know and love today including uh you know secure traffic on the internet as well as ethereum slightly harder is claims of the form I know a private key corresponding to one of Alice Bob or Charlie's public keys this is a claim that is oftentimes in the literature referred to as a group signature or a ring signature it's something that we do have cryptographic protocols for they are special purpose built for these kinds of claims and this is something that was you know invented uh you know soon after the ability to make claims like I know a private key corresponding to just Alice's public key and this kind of claim requires you to use a different

cryptographic protocol it requires you to use different myth from the first kind of claim um and this math depending on the scheme that you use might not even be compatible with the verse kind of claim in other words you need a different kind of key registry a different um you know public private key generation algorithm in order to make claims like this uh versus that first claim one thing though that uh I want to note here is that we have another way today of getting to claims like this via tools like ZK snarks with DK snarks rather than having to invent an entirely new mathematical protocol in an entirely new key generation algorithm we can simply add a few lines of code to our ZK circuit so

if I have a ZK friendly primitive for that first kind of claim I know a private key corresponding to Alice's public key I can use that to build up to this idea of a group signature with just a few lines of ZK snark code in particular you know I can add the lines for example I can I can essentially make a ZK proof of the statement I know some private key corresponding to a public key that I'm going to keep hidden and that public key minus hash one times the public key minus hash two times the public key minus hash three is equal to zero and because all of this is being done in zero knowledge what this is allowing me to prove is that with that same key generation scheme

I can prove that I know a private key corresponding to one of hash one hash two or hash three um so it's much simpler it's much more compatible uh and um yeah next slide and it enables us to go even further so for example you know we can get into claims that are even more complex such as I know a private key corresponding to one of Alice Bob or Charlie's public keys and I can toggle the property that the other people involved in this anonymity set if they want to prove that they did not sign or author this message they can or cannot do so so an example of this might be like you know I might sign a message signed by one of myself Alice or Charlie

if Charlie wants to later on reveal that he did not sign that message then he can do so he can disavow the message so this property of disavowel is something that requires you know further iteration on top of those existing cryptographic Primitives if we're looking at the non-zk Stark uh kinds of schemes you have to go to a cryptographer they have to invent some new math they have to invent a new protocol and then you're able to make claims like these again in ZK snarks however this kind of property is enabled by simply toggling on or off one or two lines of ZK circuit code and you can make this compatible with your existing key registry systems finally we get to claims that you know

can be just arbitrarily complex imagine things like I know a private key corresponding to Alice Bob or Charlie's public key and I either possess a signed attestation from one of these attestation providers David even Fred or during a block with header X I knew the private key corresponding to an account that held at least 32 eth and and you know you can imagine changing arbitrary predicates to this kind of thing um and you know I think it's quite fair to say that there's no cryptographer in the world you can go to with this kind of statement who would be able to come back to you with a mathematical paper explaining here's a cryptographic protocol for how you would prove this special purpose claim um but again with ZK snarks this kind of claim is something which you can break down into these very modular pieces that

compose on top of each other I build a ZK snark circuit for a Merkel inclusion proof I prove a snark circuit for uh you know knowledge of pre-image of a public key uh and I can put all of these things together so I think the you know one way to describe what's going on here is that ZK snarks are turning what were previously math problems around inventing new math to build new cryptographic protocols for special purpose claims it's turning these math problems into programming tasks now if I have a new kind of claim that I want to make I have a programming language for expressing that claim and generating a protocol that allows me to prove it cool thing number two that is closely

related to cool thing number one is that ZK adds interoperability to cryptographic systems so to explain what this means I first want to define a couple of terms um first off there's this idea of snark friendly cryptographic Primitives versus snark compatible cryptographic Primitives snark friendly cryptographic Primitives are cryptographic Primitives like hashing algorithms signature algorithms encryption algorithms Etc that are built specifically to be very efficient to run inside of these ZK snark kinds of environments however most of the cryptographic systems that we use today were invented before ZK snarks were even discovered so at least

in the near term our most widely used cryptographic systems will not be Stark friendly and yet we would still be able to benefit a lot from being able to build on top of these systems this larger language of expressive claims so an example of a system that's out in the wild includes things like you know key distribution and identity Registries such as uh you know pgp key registries um another example is you know if you've ever used GitHub before you've likely uploaded an SSH key that's either you know an RSA public key or an ed 25519 public key these schemes again are widely used throughout the world however

they're not engineered to specifically be smart friendly and finally you know ethereum itself uses the ecdsa signature algorithm and uh this is something that was built into the protocol before we had access to these more powerful ZK enabled tools so what we still can do with all of these cryptographic systems is we can still make them snark compatible and the way that we do that is by implementing these cryptographic algorithms inside of ZK snark circuits once we've done that we can use them as larger building blocks to make these more complex claims and our expressive claim language that ZK snarks provide us it'll be less

efficient but it allows us to reconcile for example RSA schemes with ecdsa schemes it allows us to make group signature claims around rsa-based Registries etc etc so both of these cool things are examples of the power of programmable cryptography which we can now get to defining and talking about uh in more concrete specifics so the way that I describe this idea of programmable cryptography is that it is cryptography that can be layered on top of arbitrary computations rather than just specific purpose-built claims and to contrast this with what we have so far as we've seen in the previous examples for most of cryptography's

Short History the set of mechanisms we've been able to instantiate with cryptographic tools has been very narrow I can make claims about very specific types of predicates such as this message originated from Alice or I can generate these very uh specific purpose-built read access permission system such as you know encryption which enables me to have a guarantee this message can only be read by Bob but every new specific mechanism needs a new special purpose-built mathematical protocol in contrast as we've seen with this example of identity claims new cryptographic tools allow us to have a much more flexible and Rich and

expressive design space for the kinds of claims that we can prove or the kinds of mechanisms we can enforce with cryptographic security so with ZK snarks we just saw the example of moving from only being able to make statements like this message originated with Alice to now being able to compose arbitrary identity predicates oftentimes in interaction with stateful systems together uh with tools like witness encryption we can enforce much more complex predicates on who can read data so for example we can move from the world where we can enforce guarantees like only uh a coordinator with a specific public key can read some secret vote that a participant Charlie has published um you know to do so Charlie might encrypt this secret vote with the coordinator's public key but now we can move to things

like 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 who are less permissioned will be able to partially decrypt maybe a week from now and finally smart contracts are also an example that I think spiritually lines up with this idea of programmable cryptography as we've moved towards programmable blockchains we've been able to move from the idea of coming to consensus on a special set of data Transformations that are extremely narrowly specified such as Bob can decrement his balance by 100 ether to increment Alice's balance by 100 ether to this world where we're now able able to execute arbitrary computations inside of

consensus and compose predicates together for example at Block B 100 ether will be available for withdrawal by Bob so long as Bob has closed his position in X smart contract and blah blah blah you know you get the point here so we can see that ZK snarks are examples of programmable cryptography in that they allow us to move from proofs of specific claims to a general purpose language for claims smart contracts allow us to come to consensus on uh data transformations of arbitrary complexity with Turing complete languages things like witness encryption allow us to move from Worlds where we can permission data to only be read by specific sets of public keys that we specify towards a language for specifying arbitrary predicates for read

permissions and in the future we have even more complex tools such as fully homomorphic encryption multi-party computation IO maybe even things that we haven't even conceived of yet um you know and other teams kind of have different names to label what kind of underlies all of these systems for example the Cersei team which is working on a ZK circuit compiler calls these things computational crypto systems so finally I want to talk a little bit about why I believe that there is a very natural marriage between programmable cryptography and blockchains I think a priori this is not obvious except in so far as smart contracts are kind of an example of spiritually what's going on

with programmable cryptography you know it seems like you'll have ZK circuits fully homomorphic encryption Etc on the one side you have this idea of building these very powerful consensus engines on the other side what's really the relationship between these two things so to set up this argument I first want to sort of illustrate an image or like a visual that I have in my head for what uh ethereum you know starts to feel like in a couple of years so in my head the image that I have for ethereum in a couple of years is that it is a massive coaxial cable that's carrying the world global stream of Consciousness all of Humanity's promises bets Secrets debts dreams all of these things wrapped up in

this fat gigabyte per second coaxial cable that anyone in the world or any Computing device can hook into uh you know at any point basically so in order to uh build this coaxial cable we've had to make a few design decisions in particular one thing that both enables this coaxial cable to exist but also is a major weakness is that this stream is completely transparent and that's a design decision because in order to achieve uh in order to build legitimacy for this particular coaxial cable this particular set of hashes that is flowing through the global stream of consciousness

this stream of Consciousness needs to be auditable it needs to be verifiable unfortunately this brings with it a lot of weaknesses in particular there are a lot of mechanics that require things like information asymmetry or fine-grained permissions uh in order to even function and I claim that you know when we talk about the weaknesses of the transparency of This Global coaxial cable the weakness here is not just one of privacy which I think a lot of times people might frame as an ideological issue it is also an issue of mechanics there are certain coordination systems that don't function unless people have different types of access to data or the ability to execute on that data

so one way I kind of think about this in terms of analogies is uh what programmable cryptography allows us to do is it allows us to enforce and write read write execute permissions on this canonical data stream ZK snarks might permission you know who is able to read this data and even if you can't read the data you can still verify that it is being written to properly in accordance with a set of rules that you're executing um and to give an example of this uh and why this is important you know maybe one toy example I'll bring up here is the idea of games so we when we talk about games like poker incomplete information games where people simply need to have different sets of knowledge in order for the game to be fun

um we see Dynamics like you know you can imagine in poker it wouldn't be a very fun game if everybody could see everyone else's cards and the fact that my cards are private to me is again not a matter of just ideology it's a matter of making the damn thing work at all so up until very recently the only games that it was possible to build on top of these transparent data streams like blockchains were complete information games where everyone can see every you know item move strategy that everyone else is uploading to the blockchain and there can be no secrets that players are holding from each other with DK snarks we can now introduce the notion of information asymmetry to uh this decentralized game

while simultaneously ensuring that everyone trusts the game is proceeding according to the rules that have been set out and fairly agreed upon at the beginning so for example one project that we work on is a game called Dark Forest which is a space MMO RTS game uh that you know sort of resembles Starcraft but everything is on the blockchain and the way that we enforce what is known as the fog of war in other words that your the location of your base is not freely accessible and known to everyone else is through ZK snarks and you can kind of see here there's a general pattern for how to use EK snarks to introduce certain limited kinds of information asymmetry to introduce more powerful kinds of information asymmetry

or more complex sorts you need these more powerful tools potentially like fully homomorphic encryption or multi-party computation Etc so in the future how do we move from uh being able to make these simple operations on toy environments like games to converting this transparent global data stream into a trans into a data stream that still is seen as highly legitimate and accepted by everyone uh and something which everybody knows is operating in accordance with the rules that were set out at the beginning but still enables things like asymmetry in terms of read write or execute permissions you know we want to end up in a world where we can have interactions like I walk into a store and perform a cryptographic handshake with a merchant and a multi-party computation with an identity provider

after verifying their identity I give them one token that permissions them to access some specific data on my preferences for a limited period of time 60 minutes and another that allows them to transfer a limited amount from my balance then I update my transaction history which is committed to on-chain but which is only visible to myself an interaction like this today would not be possible with a transparent data stream version of blockchains that we're familiar with now but with programmable cryptography each of these interactions can be broken down into things where a ZK snark or witness encryption or a multi-party computation might be in a might be able to enable these kinds of interactions um the last analogy that I'll kind of

make here is this idea of an Ender Chest from Minecraft so for those who aren't familiar with Minecraft um basically uh in Minecraft you can build ordinary chests which allow you to store items so I can walk over there I can you know place down a wooden chest I can put five stone blocks into it and go somewhere else and when I return to it my five stone blocks are still there um one of the most powerful items in Minecraft is this thing called an Ender Chest which is basically a chest that you can put down anywhere or where you can put down multiple versions of and they will all be tied to the same inventory no matter where you are or where you're going and that inventory is something specific to just you so if I look in the ender chest I'm going to

just see my specific items if I go over there and I put an ender chest down there I'm going to see those same specific items if someone else opens the Ender Chest they're going to see a specific inventory just for themselves and this is a super powerful tool and I think a super powerful primitive in Minecraft for enabling higher level strategies or uh you know coordination mechanisms or whatever else and I basically think that you know as more and more of our social and economic lives Move online we are going to need the tools that will enable us to build things like ender chests um that are going to enable successively higher levels of more complex systems uh and more powerful coordination mechanisms um so that's all I have for a

programmable cryptography if you're interested in learning more about Xerox Park uh applied zero knowledge or the other projects that we do you can find us online at xeroxpark.org or at the Twitter handle at xero like the numeral 0x Parc thanks so much