►
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/non-interactive-unique-nullifiers-the-key-to-the-next-era-of-zk/
ZK app systems are being held back because there isn't an anonymous way to prove that you aren't double claiming/double posting. In this talk, we explore the variety of nullifiers and present a new signature scheme that would enable things like zk airdrops or other zk systems that require uniqueness.
Speaker(s): Aayush Gupta
Skill level: Intermediate
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: nullifiers,zero knowledge,signatures
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/
A
A
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.
A
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.
A
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.
A
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.
A
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
it's
it's
non-interactive.
Anyone
could
generate
a
signature
and
blend
into
the
anonymity
Set.
You
don't
need
people
to
to
interact
and
sign
up
for
the
scheme.
A
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
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!
A
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.
A
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.
A
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.
A
Mappy
and
I've
tried
to
slightly
color
code,
the
numbers
that
are
the
same,
so
you
can
kind
of
correlate
them
across
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.
A
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.
A
For
instance,
if
you
saw
their
public
key,
you
would
obviously
know
who
they
are,
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.
A
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.
A
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.
A
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
on
the
correct
curve,
we
also
check
whatever
public
key
check
we
want
to
do.
A
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.
A
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.
A
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.
A
You
can
imagine
that
when
we
have
a
quantum
computer
with
2000
signal,
qubits
that
can
break
all
of
ethereum's
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.
A
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.
A
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.
A
It's
a
little
unclear
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.
A
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.
A
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
and
our
Twitter.
If
you
want
to
learn
more,
you
guys
are
interested
in
this,
want
to
use
a
scheme
or
are
curious
about
student
I'd
be
happy
to
talk,
and
it
would
be
really
fun
to
see
where
the
scheme
can
go.
A
C
Can
you
like
explain,
probably
maybe
using
an
example
how
like
this
non-interactive
is
like
is
like
seen
in
practice
like
in
terms
of
like
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.
A
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.
A
People
have
to
submit
their
semaphore
commitment
to
some
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.
A
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.
A
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.
C
A
That's
a
great
question
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
in
the
original
case,
and
then
you
would
claim
it
to
a
completely
unlinked
unused
account
that
has
never
had
any
transaction
on
ethereum
and
then
all
the
fire
scheme.
A
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.
D
Yeah,
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
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.
D
E
Hello,
all
right
so
I'm
wondering.
Can
you
expand
a
bit
upon
if
you,
if
you
use
this
scheme
for
a
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
transfer
of
private
assets
within
the
anonymity
Set?
Do
you
keep
that
anonymity
and
and
how
does
that
work?
E
A
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,
and
if
you
lose
that
string,
then
you
lose
your
money.
A
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
saving
memory
or
losing
strings
for
anonymous
money,
but
it
wouldn't
add
significantly
additional
anonymity
if
the
original
scheme
was
implemented
with
the
dark
pool
correctly
ascending
to
the
contract.
Yeah.
That's
a
great
question,
though,.
F
Hey
hi,
okay,
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
give
a
brief
difference
between
that
nullifier
technique
and
your
nullify
technique
for
us
to
compare.
A
Right
so
the
nullifier
technique
that
is
classically
referred
to
in
mostly
ZK
snark
posts
is
another
fire
technique
that
exists,
which
is
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.
That
is
an
added
to
a
Smart
contract
or
something.
G
Thank
you
for
the
talk.
I
had
a
general
question
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
that
an
address
is
eligible
for
an
outro
based
on
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?
A
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.
B
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
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.
A
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
the
airdrop
contract
itself
will
pay
for
the
gas.
The
way
this
would
work
is
when
you
claim
the
airdrop
contract
would
record
the
amount
of
gas
being
used
in
the
transaction.
A
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
or
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
because
it
contract
is
calculating
and
reimbursing
them
more
than
they
would
have
paid
for
the
gas.
A
A
Similarly
reimbursing
the
the
front
running
relayer
effectively
or
you
could
send
it
to
like
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,.