►
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/recursive-zk-applications-and-affordances/
Recursive zkSNARKs are poised to hit production in the next two years. We discuss how to think about the new affordances and potential applications that recursion unlocks for both scalability and privacy. These include proofs-of-proofs-of-knowledge like ETHdos, on-the-fly "programmable" SNARKs, incrementally verifiable computation, distributed proving, and tactics for reducing verification cost or proof size.
Speaker(s): Ying Tong, Nalin Bhardwaj
Skill level: Advanced
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: zero-knokwledge,recursion
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
I'm
Nolan
I'm
ingtong
and
today
we're
going
to
talk
about
recursive,
ZK
snarks,
the
kinds
of
applications
they
unlock
and
how
we
can
Implement
them.
So
first
we
should
talk
about
what
recursive
proofs
even
are
so
in
the
context
of
snork.
Recursion
is
usually
the
ability
to
verify
a
smart
proof
inside
of
another
snug
proof.
So
this
is
the
ability
to
say
something
like
I
know
is
not
proof
that
when
I
run
the
smart
verification
algorithm
on
it
returns.
A
So
now
that
we
have
this
primitive
in
mind,
we
should
think
about
the
sort
of
natural
question
is:
why
would
you
want
to
make
recursive
smart
proofs
so
typically
regular,
ZK
snarks?
You
know
we
think
of
them
as
having
two
sort
of
properties,
such
signals
and
their
knowledge,
so
recursion
in
fact
unlocks
powerful
versions
of
both
of
these
properties
in
the
form
of
compression,
which
is
a
stronger
version
of
the
cygnus
and
multi-party
composibility
from
zero
knowledge.
A
So
first,
let's
talk
about
compression,
we
think
of
compression
as
supercharging
succinctness
and
in
particular,
usually
the
applications
of
compression
tend
to
share
a
sort
of
common
pattern,
and
this
common
pattern
looks
like
you
know.
Let's
say
we
have
a
prover
who
wants
to
show
a
verifier,
some
n
pieces
of
knowledge.
How
do
they
do
this?
They
make
a
proof
showing
two
sort
of
things.
A
So
the
next
question
is:
how
do
you
make
the
smart
pool
for
the
N
minus
one
pieces
of
knowledge
and
in
fact
we
use
the
same
kind
of
strategy
again,
the
N
minus
one
pieces
of
knowledge.
We
show
one
piece
of
knowledge
and
additionally,
we
show
that
we
know
another
proof
of
n
minus
two
pieces
of
knowledge,
and
so
then
you
know
you
just
Cascade
down
this
sort
of
strategy
and
you
end
up
with
the
situation
where
you're
verifying
one
snark
proof
and
in
that
it's
automatically
verifying
these
n
items
of
knowledge.
A
Another
instance
of
compression,
that's
particularly
helpful
to
point
out,
is
the
setting
where
you
want
to
compose
between
different
proof
systems
or
arithmetizations
and
at
the
time
also
pick
the
good
features
of
each
of
them.
So,
for
instance,
you
can
have
some
setting
where
you
have
two
different
proving
schemes,
one
where
you
have
a
fast
prover,
but
unfortunately
the
verifier
is
slow
and
another
where
the
approver
is
lower.
But
you
get
the
trade-offs
that
the
verifier
is
fast.
A
A
concrete
sort
of
instantiation
of
this
interoperability
is
the
setting
which
starts
and
grot16
in
particular,
grads.
Grad
16
is
very
cheap
to
verify,
whereas
Starks
are
very
easy
to
prove.
So,
if
you
verify
a
stark
roof
inside
of
a
graphics
scene
snark,
you
end
up
with
a
proof
of
the
original
statement
with
the
fast-prover,
as
well
as
a
fast
verifier.
A
So
generally
compression
has
this
sort
of
property
that
is
very
mechanical
and
usually
you're,
rolling
up
some
giant
list
of
computation
or
items
of
knowledge
increment
into
a
single
proof,
so
just
to
give
a
flavor
for
sort
of
what
applications
this
unlocks.
Let's
look
at
things
that
are
interesting
to
roll
up,
so
first
is
signatures.
A
Over
the
summer
we
built
applications
using
sort
of
this
primitive
of
recursive
compression
of
signatures
called
isocratia,
where
we
end
up
with
a
low
trust,
low
cost
sort
of
roll-up
of
off-chain
modes
and
end
up
securing
governance
and
then
more
related
to
sort
of
blockchain
land.
You
can
do
the
same
kind
of
trick
with
light
climb
boots
and,
in
fact
plumo,
which
is
solos.
A
Light
client
is
based
on
this
sort
of
idea
and
there's
also
another
group
named
Axiom,
which
is
exploring
sort
of
more
cooler
use
cases
for
this
with
aggregating
and
providing
historical
data
through
the
use
of
recursive
snarks
and
then
finally,
the
sort
of
Hot
Topic
in
blockchain
land.
These
days
is
making
roll
ups
of
transactions.
A
Two
particular
ones
that
are
sort
of
interesting
to
point
out
are
Mina,
who
sort
of
use
this
recursion
primitive
as
a
consensus,
player,
primitive
and
polygon
Hermes,
who
use
the
exact
strategy
of
like
using
Starks
for
fast-prover
settings
and
grad,
16
or
snarks
for
fast
verification
settings?
Next,
let's
talk
about
composability,
my
personal
favorite
property
unlocked
by
recursive
Snooks.
So
to
give
some
context
for
this,
let's
take
a
step
back,
let's
think
about
what
a
normal
ZK
proof
you
know.
A
What's
the
context
of
a
normal
ziki
proof,
we
usually
think
of
you
know
DK
proofs
in
this
context,
where
approver
is
showing
knowledge
to
a
verifier
without
revealing
the
underlying
fact
of
the
knowledge
with
recursion.
In
fact,
you
can
unlock
something
more
powerful.
Approver
can
show
knowledge
to
a
verifier
without
fully
knowing
the
underlying
facts
themselves,
so
this
is
a
bit
hard
to
model,
so
I'll
just
lead
with
an
example.
Over
the
summer
we
build
this
application
called
eat.
Dos,
which
is
a
dash
number,
is
on
social
graphs.
A
So
these
social
graphs
are
sort
of
graphs
of
relationships
of
people.
Saying
I
am
your
friend
kinds
of
things
and,
for
instance,
here
we
have
this
graph
and
vitalik
sent
someone
who
sends
someone
who
sends
someone
and
finally,
I
ended
up
with
a
four
degree
path
to
vitalik.
Now
I
can
prove
that
I
have
a
four
degree
path
of
italic
without
reviewing
any
or
without
knowing
any
of
the
intermediate
parties
in
this
path.
So
how
do
I
do
this?
A
The
the
phrase
starting
point
we
thought
of
was
games
like
telephone
or
Chinese
Whispers,
where
you
know
you
pass
a
word
around
or
something
and
you
want
to
make
edits
to
it
incrementally,
and
then
you
can
make
more
complex
applications
like
party
games
like
Mafia
those
kinds
of
things
and
then
more
relevant
to
blockchain
land.
You
can
build
private
State
channels
and
roll
ups
of
that
sort.
B
So
now
that
we
have
some
intuition
for
the
high
level
properties
of
recursive
proofs
and
now
that
we've
seen
some
classes
of
applications
that
are
enabled
by
them,
you
might
be
feeling
that
recursive
proofs
are
kind
of
unreasonable.
We
get
unlimited
compression
and
compostability,
so
I
guess
the
natural
question
now
is:
how
do
we
Implement
and
construct
these
systems?
B
So
right
now,
there's
broadly
three
classes
of
recursive
proofs
in
production
and
as
we
descend
the
hierarchy,
we
are
relaxing
the
requirements
on
the
proof
systems
which
are
eligible
for
recursive
schemes.
So
at
the
very
top
of
the
hierarchy
we
have
really
the
most
stringent
requirements.
So
we
we
need
proof
systems
with
verifiers
that
are
sub-linear
that
are
succinct
in
the
size
of
the
statement
being
proven,
and
this
enables
us
to
do
full
recursion
at
every
recursive
step.
B
So
if
we
relax
our
requirements
a
little
bit-
and
we
say
even
if
we
don't
have
a
succinct
verifier-
maybe
we're
happy
enough
just
with
a
succinct
accumulator,
so
intuitively.
What
this
means
is
that
we
want
a
verifier
with
this
shape,
that
they
have
a
succinct
check,
a
cheap
check
and
then
separately.
B
They
have
an
expensive
check,
and
so
here
we
can
instantiate
an
atomic
accumulator
and
at
each
recursive
step
we
only
perform
the
succinct
checks
and
we
accumulate
the
expensive
check
and
delay,
checking
it
until
the
end
of
a
long
batch
of
proofs
and
doing
this
gives
us
amortization
of
the
expensive
check.
And
finally,
if
we
relax
even
more,
we
don't
even
require
a
succinct
accumulator.
B
Well
now
we're
just
happy
with
a
succinct
public
accumulator,
and
the
idea
behind
this
split
accumulation
is
simply
that
you
split
your
accumulator
into
a
public
and
private
part,
and
the
public
part
is
short,
and
this
is
what
we
accumulate
at
each
recursive
step
where,
whereas
we
delay
the
verification
of
the
private
part
of
the
accumulator
until
the
very
end,
so
let's
go
through
these
constructions
at
a
high
level,
one
by
one.
Just
so
you
can
see
the
shape
of
it.
So
probably
the
cleanest
shape
is
the
the
cleanest
shape
would
be
full
recursion.
B
So
over
here
we
start
with
our
application
circuit
and
it's
f.
F
of
w-I-z-I
gives
you
z.
I
plus
one
right.
It's
a
normal
relation.
Now
we
bundle
that,
together
with
a
recursive
verifier
and
basically,
this
recursive
verifier,
takes
in
a
proof
instance
that
was
produced
by
the
previous
instance
of
the
recursive
circuit.
And
so,
if,
if
we
look
forward,
we
we
need
to
generate
a
proof
of
the
whole
recursive
circuit
in
order
to
input
to
the
next
recursive
instance.
B
So,
in
this
way
we're
chaining
recursive
circuits
and
at
each
step
we
are
fully
verifying
the
previous
instance,
and
when
we
get
to
the
final
verifier,
we
no
longer
need
to
bundle
it
with
the
applications
are
getting
here.
We
can
just
perform
a
final
verification
of
the
proof
outside
the
circuit.
So
this
is
full
recursion
is,
is
the
cleanest
API?
B
Now
we're
gonna
get
slightly
more
messy
and
we're
gonna
relax
our
requirements
to
get
an
atomic
accumulation
scheme.
So
now,
if
you
recall
here
an
atomic
accumulation
scheme,
our
verifier
is
not
sublinear.
So
in
fact,
the
verifier
inside
the
recursive
circuit
is
just
the
accumulation
verifier,
and
it
only
concerns
itself
with
the
succinct
checks
of
the
verifier
and
the
expensive
check
is
accumulated
and
deferred
at
each
step.
So
here
we
are
chaining,
basically
instances
of
proofs
and
accumulators
and
at
each
step
we're
just
procrastinating
on
performing
the
expensive
check.
B
But
at
this
point
we
can
do
it
outside
the
circuit
and
at
this
point
the
cost
of
the
linear
time
check
is
amortized
across
a
big
batch
of
proofs.
Now
from
here
to
Atomic,
accumulation
is
just
a
small
step.
So
it's
just
splitting
up
your
accumulator
and
your
proof
instance
into
a
public
and
private
part,
and
now
the
verifier,
the
recursive
verifier
gets
even
smaller,
and
it
concerns
itself
only
with
accumulating
the
instances,
the
public
parts
and
it
does
not
perform.
B
So
a
lot
of
these
constructions,
I've
described,
are
really
cutting
edge
and
they
come
from
a
feature
of
our
modern
proof,
systems
that
are
very
modular
in
design
and
as
we
get
a
better
understanding
of
the
building
blocks
and
the
components
of
our
proof
systems.
This
lets
us
customize,
our
proving
Stacks
with
a
lot
finer
granularity
and
recursion,
as
we
saw,
also
allows
us
to
compose
proof
systems
and
to
get
the
best
of
both
worlds
in
many
cases.
B
So
here's
an
example
of
a
modular
conception
of
a
proof
system,
so
I
work
on
the
proof
system,
Halo,
2.
and
I.
Think
of
Halo
2
in
terms
of
these
four
components
so
at
the
very
front
end
is
where
you're
interfacing
with
your
business
logic.
So
you
take
a
relation
and
you
arithmetize
it
into
so
in
in
Halo
2's
case,
we
encode
our
values
in
the
LaGrange
basis
and
we
encode
constraints
on
these
values
as
polynomial
identities.
B
We
then
input
these
polynomials
into
this
information,
theoretic,
polynomial
IOP
that
basically
checks
the
correctness
and
the
consistency
of
the
polynomials
encoding
our
circuit,
and
then
we
realize
this
polynomial
IOP
using
a
cryptographic
compiler.
So
in
this
case
it's
the
inner
product
argument
that
and
the
Fiat
Shamir
transform
that
allows
the
proverb
to
Define
their
interaction
with
the
verifier
and
at
the
very
end
of
it.
Halo
2
is
a
recursive
group
system
and
we
can
in
fact
instantiate
an
atomic
accumulator
over
the
inner
product
argument.
B
B
B
Another
way
that
we've
seen
before
in
this
presentation
is
more
or
less
just
implementing
verifier
X
and
prover
Y,
and
you
would
do
this
also
for
efficiency
gains
and
sort
of
the
last
Clause
of
composition
that
I
came
up
with
was
really
just
thinking
up
better
cryptographic,
compilers.
So
there's
this
recent
paper
by
a
group
at
consensus
and
they
they
took
this
protocol
gkr.
B
So
what
the
team
at
consensus
did
was
they
came
up
with
their
own
cryptographic,
compiler
that
was
custom
made
for
their
target
proof
system
and
the
target
proof
system
here
is
like
a
growth.
16
r1cs
per
system,
and
so
really
like
that's
going
in
the
middle
and
making
changes
like
customizing
proof
systems
at
a
very
low
level
for
efficiency
and
yeah.
I
think
this.
B
So
you
can
think
of
this
as
kind
of
a
call
to
action,
so
I
think
there's
certain
nice
to
have
certain
to
Do's
that
all
proof
system
implementers
would
really
like
the
first
being
good
benchmarks.
Fair
benchmarks
of
heavily
used
Primitives
like
hash
functions
like
big
and
arithmetic,
so
benchmarks
of
these
Primitives
across
different
proving
stacks,
and
the
second
would
be
it's.
A
kind
of
a
meta
requirement
is
to
think
of
like
what
metrics
we're
interested
in,
for
example,
efficiency,
for
example,
proof
size
and
basically
how
to
optimize
towards
these
Magics.
B
So
on
what
basis
are
we
comparing
different
compositions
and
configurations,
and
the
last
sort
of
call
to
action
would
be
to
think
carefully
about
how
security
properties
also
compose
like
excuse
me
like?
Is
it
the
least,
secure
approved
system?
The
the
fewest
bits
of
secure
30
or
like
some
weird
composition
when
we
mix
and
match
proof
systems.
B
So
all
these
are
questions
that
it
would
be
great
to
have
everyone's
input
on,
like
even
this
taxonomy,
that
I
came
up
with
I'm,
not
sure
that
it
captures
all
features
of
proof
systems
in
the
best
way,
so
Nolan
and
I
actually
help
out
at
a
group
called
Xerox
Park.
Oh,
we
didn't
put
the
name
on
the
slide.
It's
0x
Park
and
there
we're
setting
up
this
task
force
to
look
into
this
area
of
recursion,
aggregation
and
composition,
yeah
and
I.
C
Well,
thank
you
so
much.
We
have
time
for
one
or
two
questions.
If
you
have
any
questions,
please
raise
your
hand.
We've
got
a
question
here
on
this
side.
Hi
I
didn't
think
this
would
work
for
years
and
years
and
years
and
I
also
I'm,
not
I'm,
not
even
sure
that
does
work.
It
does
seem
way
too
good
to
be
true.
So
can
you
prove,
and
how
do
you
prove
that
that
it's
secure
to
do
recursive
like
proofs
like
this
like
where?
Where
is
the
security
proof?
B
A
A
D
So
recursive
proofs
are
real
fun,
but
if
you
do
it
at
scale,
then
you're
you
know
it's
like
you,
you,
you
have
skill
and
corruptus
snapping
at
your
heels
because
of
the
proof
carrying
data
right.
If
you
want
to
build
on
recursive
proofs
and
it
doesn't
happen
at
the
same
time,
so
let's
say
you
do
a
proof
and
you
do
recursive
proof
and
then
you
have
to
wait
for
a
state
change
for
something
else.
It
might
happen
much
later.
D
B
Yeah
yeah
for
sure
I
think
I,
don't
think
recursive
proofs
are
a
silver
bullet
and
I
think
they're
better
suited
for
some
shapes
of
applications.
So
recursive
proofs
are
very
commonly
used
to
reduce
proverb,
space
complexity,
so
breaking
up
a
large
circuit
into
many
smaller
parallelizable
circuits,
so
yeah,
but
I
I
agree
like
in
context
of
applications
with
more
complicated
and
like
timely
data
flows.
It's
it's.
We
have
to
put
some
care
into
how
and
where
we
are
inserting
this
proof
carrying
data
yeah.
A
Right
and
also
just
to
add,
I
think,
there's
also
some
interesting,
like
sort
of
clean
separation
here
of
like
rules
versus
data
availability,
sort
of
problems,
and
if
you
just
look
at
you
know,
data
availability
as
a
sort
of
Black
Box
problem.
You
know
you
have
lots
of
blockchain
kinds
of
solutions
for
it
and,
for
instance,
isocratia
explorers.