foreign
[Music]
knowledge airdrop in which you enable
Anonymous governance where people's
votes aren't impacted by other people's
votes where people can vote
independently and they're only revealed
once you want to tally the votes or once
the voting period is over in order to do
this to do a zero knowledge airdrop you
need a way to avoid double claiming that
is people can anonymously claim their
tokens to an unlinked account but still
there's some identifier that represents
them that prevents them from claiming
the same airdrop twice or maybe we want
to do an anonymous Message Board in
which we know that each of the people
cannot be identified but we know for
instance that maybe the first poster is
the same as the third poster or imagine
we want to do Anonymous voting within a
large anonymity set such that the very
first person to vote has the full power
of every single person in this anonymity
set
or really any civil resistant Anonymous
application so we thought about what we
could use to be this kind of tool that
stops us from double spending and it's
kind of unique identifier of someone on
chain and after talking a bunch on
Discord we decided to create a new Zeke
nullifier scheme on ecdsa this is Joint
work with Persona Labs geometry research
and originally done at Xerox Park and
MIT so to kind of clarify what exactly
this nullifier is let's try to maybe go
through some properties
so if you want to avoid people from
double spending and we want each person
to claim only once then we need this
property this this identifier outputted
by this account to be unique that is
everyone should have a different one we
also want this value to be deterministic
that is if I have some ethereum
public-private key pair I should only be
able to generate one of these signals
finally the signal I generate should be
verifiable without access to my secret
key this is because in a ledger wallet
or in a secure Enclave it's not possible
to even read the secret key or take it
out of the secure Enclave we also don't
want users copy pasting their private
Keys all over the place
and finally we want this number this
scheme to be completely non-interactive
if you've heard of nullifiers before you
might have heard of something like
tornado cache or semaphore and the way
that works is that as people sign up the
anonymity set grows bigger and bigger
and bigger however the first person to
use tornado cash or the first person to
sign up for a semaphore group has zero
anonymity until more people join but if
we want the full power of the entire
anonymity set for the very first person
we need the scheme to be non-interactive
that is there shouldn't be two phases
like a sign up phase and a utility phase
so to understand these properties a
little bit more one useful exercise is
to go through some examples of schemes
that may work or may not work so imagine
when we wanted someone to post this
deterministic value that identified
themselves that stop them from double
claiming or stop them from double voting
but they use the hash of a deterministic
ecdsa signature
now you might guess that this has all
the properties we want it's Unique if
you're signing a message a deterministic
signature there should only be one
um it's it's uh non-interactive anyone
could generate a signature and blend
into the anonymity Set uh you don't need
people to to interact and sign up for
the scheme first however the issue of
determines the ecdsa signatures is that
you cannot verify that a deterministic
ecdsa signature was generated with the
correct deterministic Randomness unless
you have access to the private key that
is deterministic EC Dasa signatures are
identical to non-deterministic ecdsa
signatures because the randomness is
like the hash of the private key and so
if you're trying to verify this on chain
or in a ZK snark you would need the
private key so it doesn't quite achieve
what we want it to achieve a second idea
is this idea called a verifiable
unpredictable function or a unique
signature now the vast majority of the
schemes for these are on pairing
friendly curves and
ethereum which is on ecgsa on SEC B 256
K1 is not a pairing friendly curve so
the vast majority of this literature is
fairly inaccessible to us we could try
something like hash of message from a
public key you'd imagine this is unique
every account every public key has a
different value of this hash it's
deterministic if you have a public key
and there's some message say the app ID
then this hash is deterministic
it's verifiable without your private key
and it's not interactive you can give
this hash without signing up in advance
now the issue with this is that it's a
little bit subtle but it's actually
possible to de-anonymize people who are
using this for anonymity
the way you do that is you can take the
list of all 200 400 million private keys
on ethereum calculate the hash values
for every single one and match it up
with this nullifier value on chain and
boom you've de-anonymized a person who
tried to use this as their unique
identifier
maybe kind of getting inspired by this
we can try something like hash of
message comma secret key
you'd imagine this is similar to the the
public key case except
you can't take everyone's secret key on
chain because you don't know everyone's
secret key so it's not possible to
anonymize people in the same way
but the issue is to verify something
that's behind a hash you have to
calculate the entire hash function
inside the xero knowledge proof or
inside whatever identity primitive
you're using and we don't want to use
this copy around the secret key and so
this scheme isn't quite it
so finally we resolved on this scheme we
use a hash of message from a public key
to the power of secret key it's kind of
similar to the other schemes but it
turns out it has this nice property that
is a ddh vrf or a decisional
diffie-hellman verifiable random
function and specifically what this
means is that we can verify that this is
actually calculated correctly without
access to the secret key so to maybe
summarize like what exactly the
properties we are that we want so far is
that we want this deterministic function
of a user's secret key that can be
verified with only their public key and
keeps them anonymous
and the way we do this is we Define a
new deterministic signature scheme on
ethereum so I'm going to try to go
through what exactly the signature
scheme is and so this is going to get a
little bit Mappy and I've tried to
slightly color code the numbers that are
the same so you can kind of correlate
them across
um and although the math is a little bit
difficult to understand on first glance
I'll try to give you an intuition for
why it achieves the properties that we
wanted to achieve
so remember our nullifier was the hash
of message from a public key to the
power of secret key
and so this value will be public it will
be calculated inside the user's wallet
whether it's our metamask or their
Ledger or anything else and this value
will stay public the entire time it will
be posted on chain eventually for
everyone to see
these private outputs will be created by
the wallet and given to the user these
outputs if they were seen by the
external world could de-anonymize a user
for instance if you saw their public key
you would obviously know who they are
um
and so the idea is that these signals
are kept to the user and the user can
use them to generate a ZK snark so what
the user does is once they have these
signals you can think of this as
splitting the signature scheme into a
deterministic part the nullifier and the
non-deterministic part the private part
the verifier simply checks these values
are calculated correctly
now it's a little bit hard to drive
through all this math so I'm going to
try to give like a high level overview
of why we have this kind of C value
floating around now the reason we have
this like C value floating around is
that when you're taking a hash it's
impossible to Brute Force the output of
the hash so you must know all the inputs
that went into the hash this means that
the person you can kind of think of this
C commitment as a hash commitment to
these values of G to the r to another
fire to our public key then we calculate
this value which is s which is based on
the C value which we know must have been
calculated after c
and notice that this s value does not
reveal the user's secret key although it
has secret key in it it's blinded by a
completely random number the check in
the snark you'll also notice has no
secret keys in it we only pass in these
signals none of which you can use to
derive the user's original secret key
and the check that we do is effectively
did the user calculate C in the correct
order did they commit to their secret
key their public key and calculate the
signature in a way that would have
actually proved that they owned that
secret key and finally the ZK snark
apart from checking that the nullifier
was calculated correctly in a German
succession
um on the correct curve we also check
whatever public key check we want to do
this allows us to verify that the public
key is in fact acting correctly and has
some unique identifier but now I have to
verify that the public key is in fact
allowed to interact with this protocol
maybe they're a numerical proof maybe
they submit a Merkel try Patricia proof
that they are they satisfy some
condition on chain and the idea that we
would also lump this in with the
verifier check in the ZK snart so to
summarize the wallet generates these
signals the user plugs them into a ZK
snark and posts the ZK snark when with a
public nullifier output on chain proving
that they are allowed to interact with
this protocol and a unique user who is
still going to be kept Anonymous now
interestingly when we were doing this
work we discovered this Quantum secrecy
interactivity trade-off now it turns out
that semaphore is extremely Quantum
secure because it uses hashes but it's
not it is interactive meaning that you
have two phases and the first people
interact they interact with the protocol
have no anonymity
our scheme on the other hand is fully
non-interactive the very first person to
use another fire will have the full
anonymity of the entire anonymity set
however it is not Quantum secure
and the way that you can kind of think
about Quantum adversaries in the
situation is that a Quantum adversary
can effectively take discrete log and
prime factorizations but it can't undo
hashes
you can imagine that when we have a
quantum computer with 2000 signal qubits
that can break all of ethereum's uh
public keys and derive their private
keys
in the actual situation of the chain
continuing this is completely fine users
can sign their new key with their old
key before Quantum Supremacy occurs and
the entire chain can move seamlessly to
a new Quantum resistance system
however if you can derive all the user
secret Keys then if you remember the
trick we did in the very beginning where
we calculate the half of meshes come a
public key for all the users and
de-anonymize people we can do the exact
same thing with this Quantum adversary
calculated secret key Quantum adversary
simply calculates every secret key for
every private for every public key in
ethereum calculates another Fires for
every single one of these keys and
matches them up with the anonymous
signal and so interestingly any future
Quantum adversary can break past
anonymity
um
and the issue is that actually any
deterministic nullifier scheme that has
the properties that I defined in the
beginning has its vulnerability because
if you Source Randomness from only the
secret key that means the quantum
adversary can derive it as well and so
you have to Source Randomness beyond the
secret key which requires the user to
remember that value which means you need
to have a password so to kind of get a
better intuition for like whether this
actually matters or not
there's the the predictions of quantum
researchers very extremely widely some
researchers have mentioned they think
it's going to come as soon as 30 years
signal qubits that can break ecdsa some
researchers think somewhere around 100
years and some think that because of the
noise problem it's theoretically
impossible and it will never happen
um
it's a little unclear uh as of right now
we have about 20 signal qubits and we
need over 2000 to break ecdsa
so I've written a short mental model
that you can read once you look at the
link on the slides which describes kind
of how I think about this Quantum mental
model of how these systems are going to
evolve and whether or not we should be
worried about it but I think for now the
decision that we made is that
it makes more sense to not be worried
about Quantum oracles because as long as
the protocols are transparent that you
will be genomized in something between
30 and 100 years the idea is that most
people probably won't care because by
that time for instance even governments
declassify their secret documents in
this kind of time frame
so to understand more how this another
fire scheme is going and if you can use
it yourself we have a paper in which we
approved all the security properties of
this nullifier scheme
um we have a blog post that's going to
be coming up on the Persona Labs blog
soon and we also have a proof of concept
uh in Rust and in a metamask snap
finished
um the next step is to put it into a ton
of other wallets into Ledger into burner
wallets into metamask core create an ERC
standard for people to use this scheme
so we can have unique anonymity across
the board and to potentially write an
appendix to an ietf RFC to make it a
complete standard across all of
cryptography if you're interested in
seeing more about the code this link
will link you to our GitHub repo where
we have all the open source code we'll
be linking to all the slides here as
well along with the quantum mental model
um and our Twitter if you want to learn
more
um you guys are interested in this uh
want to use a scheme or are curious
about uh student I'd be happy to talk
and it would be really fun to see where
the scheme can go if anyone has any
questions about understanding the scheme
or thoughts on where it can or can't be
used I'd be happy to take any questions
for the next five or ten minutes
test okay how is this scheme called
so right now the scheme is called just a
ZK nullifier because we think this is
the kind of most straightforward way to
describe what is going on but I'm open
to any other name suggestions
I think there's a question in the front
can you like explain uh probably maybe
using an example how uh like this
non-interactive uh is like is like seen
in practice like in terms of like uh
using the scheme
like maybe like an airdrop like can you
explain like how that system would work
how like user would interact and like
kind of maintain that property yeah
that's a great question I can maybe go
through the kind of the whole airdrop
scheme and try to describe why it
wouldn't be practical or something like
that before but why it could be
practical with something like the
nullifier so if you imagine the
semaphore scheme for the airdrop the way
it would look is that people would first
have to sign up to receive the airdrop
and this is so people have to submit
their semaphore commitment to some uh
either like an on-chain directory or an
off chain list and the issue with this
is that people can then stable attack
this airdrop very easily because they
know that an interrupt is going to be
coming and this is a way to gain
eligibility for it and so because they
have this two-step process people can
spam whatever mechanism it is that
they're using to determine who is
legible and who is not resulting as
being of somewhat impractical solution
you can also imagine that if you didn't
have a two-phase process where instead
people could sign up for the summer for
Keys whenever and claim whenever and the
very first person to claimed the airdrop
was sign up for this timer for key you
would see only one semaphore key in the
list of all summer Four Keys and then
that person would clean their airdrop
and so you would know that the person
who posted that proof must have been the
person who claimed the airdrop and so
there's all the small anonymity set is
is not ideal if you're trying to
maintain perfect anonymity for everyone
in the set with another fire scheme
would work is that when you claim the
airdrop you prove that you have another
fire for a message like I am claiming
the ZK airdrop and the verifier would
prove that you in fact signed that
message that you created your
deterministic nullifier correctly and
would allow you to clean the airdrop and
then add that nullifier to a block list
from ever claiming again and so what
would happen is the very first person to
claim no one would know who they are out
of the entire set of all the keys that
are eligible for the airdrop
where does the like nft eventually end
like it's an ethereum address versus uh
like is it like the things are happening
on chain or is like an off chain process
or like uh just trying to understand
that yeah that's a great question uh for
those who don't hear the beginning the
question was basically how does ZK
airdrop actually implemented and the
idea is that what you would do is you
would prove that you own an account that
is in the Merkle tree of eligible
addresses for the SDK airdrop you would
generate a summer for another fire for
that scheme uh in the original case and
then you would claim it to a completely
unlinked unused account that has never
had any transaction on ethereum
um
and then all the fire scheme you do a
similar thing you would prove you have
an account in this Merkel tree you would
prove ownership of that account you
would prove the nullifier Via this is
another fire scheme and similarly the
tokens would go to a completely new
fresh ethereum account and there's no
history on it and it's effectively
anonymous
that's a great question though
yeah uh so just to expand on the
previous question like a concrete
example so you wanted to like airdrop an
NF an nft to anyone who has a crypto
Punk and but you want people to be able
to claim it without revealing which Punk
they are
um within semaphore or anything that's
like a two-step your anonymity set is
only going to be the amount of people
who like sign up for this mm4
and with this the anonymity even if it's
just two people that end up claiming
this nft they have the full anonymity
set of like all all Punk holders if that
makes sense and it's going to like a new
address not to the one that has the punk
hello all right uh so I'm wondering uh
can you
um expand a bit upon if you uh if you
use this scheme for a uh sort of a
multi-step protocol where it's not just
maybe a tornado cache deposit and
withdrawal or a claim scheme but you
continue where you maybe have some sort
of um transfer of private assets within
the anonymity Set uh do you keep that
anonymity and and how does that work
yeah so the the way dark pool transfers
would kind of work with its anonymity
with this nullifier is that
the way most people enter a dark pose
they send their assets to like a
specific smart contract and so you
already know that the engine reset is
limited to everyone who has ever
interacted with a smart contract and one
thing you could do is you could use
something like semaphore and if you
interact with smart contract the
guarantee that you have to sign up for a
semaphore key so because the anime set
is already limited by something like an
on-chain interaction the nullifier
wouldn't add additional anonymity
because it's already limited by the
chain interactions however what it could
do is prevent you from having to
memorize secret notes so for instance
with tornado cache you have to download
a string and remember it forever
um and if you lose that string then you
lose your money but
what you can do with this scheme is that
instead of having to memorize a Toyota
cache note you just remember the amount
of money you got and then you could say
okay I got one eighth so I'm going to
sign a message saying here to cash one
eth and I know that the nullify that it
creates will be a valid note for my
deposit and the contract can simply
validate that and so it can help uh
saving memory or losing strings for
anonymous money but it wouldn't add
significantly additional anonymity if
the original scheme was implemented uh
with the dark pool correctly ascending
to the contract yeah that's a great
question though
hey hi uh okay uh I'm pretty sure like
many of us would have read about
nullifies for the first time in
vitalik's article the one with like
privacy applications now and like I did
not understand it completely but I
thought it was vitalik who wrote it so
it must be true so
so can you like just uh give a brief
difference between that nullifier
technique and your nullify technique for
us to compare right uh so the nullifier
technique that is classically referred
to in mostly ZK snark posts
um is another fire technique that exists
which is uh kind of why Halo 2 defined a
number of years ago and it's kind of
evolved into being this semaphore type
scheme in which another fire just
represents that you can't double claim
or double interact with a specific
protocol because I know the fire nullify
is their ability to do so
um that is an added to a Smart contract
or something and then when you interact
with that in the future it would notice
that you've already interact with it
before and then stop that transaction
from going through
um so the scheme that likely is being
referred to that in that post is likely
a semaphore type scheme or a sign up
type scheme in which this nullifier is
like a hash or some string
um which again would have to be
interactively generated
um and so when I when I say this kind of
semaphore side or this like interactive
side that's larger than the classical
nullifier that I'm referring to yeah uh
thank you for the talk um I had a
general question
um kind of about coming back to the
example of the token get a job so if you
either use like the zika nullifa or
summer for to generate a proof um that
an address is eligible for an outro
based on
um owning an nft in a set for example
how does that respond to updates for
example when you transfer the nft
afterwards since the nullifier is only
tied to the address could you then
transfer that nft to different address
and create another another file and
again qualify for their job
yes that's a great question so the way
that you would solve this kind of
multiple qualifying for the airdrop
problem is that when you define when you
release this airdrop you define like a
strict set of keys that are eligible for
this airdrop it can be say like people
who owned a certain nft at a certain
Block in which case there's a finite
number of addresses that can claim that
or it can be so anything you could prove
in the ethereum storage Market potential
try or it could be like just a list of
addresses in a Merkel tree like a
standard airdrop is done so the idea is
that even the the reason that nullifiers
uses it would only suffice for this
claiming step because once you've
claimed the nullifier to an account and
you've claimed this nft or airdrop or
whatever to this account that account
can do whatever it wants with that
information now it's it's come from a
completely anonymous source and so it
can it can go wherever and it'll
continue to maintain that anonymity so
the you can continue to transact that
nft or your C20 but you just wouldn't be
interacting with the original airdrop
contract ever again so you wouldn't need
another fire in the future
yeah okay good so this is probably a
silly question when people redeem it
right they have to provide some gas so
the guests must be coming from some
account so even even though we have all
these anonymity is uh probably hide the
the edges that's going to receiving it
but when people provide the gas
this transaction actually links the
account that's receiving nnp versus the
account having the gas so it's still
revealing like some information yeah
that's a great question the question was
basically how do you pay for the gas
without the anonymizing yourself and
there's kind of two main ways to do this
one is uh the airdrop contract itself
will pay for the gas the way this would
work is when you claim uh the airdrop
contract would record the amount of gas
being used in the transaction there
would be a certain Bank inside the
contract to pay for that gas plus a
little bit extra and so the idea is that
you could send your claim transaction on
chain uh or uh to a private mempool an
Mev Searcher would actually be
incentivized to claim this transaction
act as your relayer in a decentralized
manner because they're getting
compensated for it uh because it
contract is calculating and reimbursing
them more than they would have paid for
the gas that's one way to do it second
way to do it with something like account
abstraction where you can again have a
third party pay for the gas usually out
of the contract this can happen with say
the contract doing an atomic swap with
say the token that it's giving you and
each to pay for the gas
um
similarly reimbursing the the front
running relayer effectively
um or you could send it to like uh uh
something like keeper Network which
would incentivize which is basically a
place where Mev Searchers can post or
people can post maybe ideas and maybe
Searchers can take them you could use a
mempool or you could use a kind of a
private centralized or decentralized
method to do that
yeah that's a good transaction that's a
great question though
thank you so much bigger Plus