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