►
Description
Topics covered
-----------------------------
0:55 - Author’s introduction
2:55 - Presentation outline
3:37 - Weak statelessness
6:48 - The difficulty with statelessness
7:55 - What is a verkle trie
9:19 - Merkle tree
11:07 - Width-4 Merkle tree
12:45 - The problem with “wide” Merkle trees
13:15 - Vector commitment
15:00 - Vector commitment example: KZG commitment
16:34 - Width-4 Verkle tree
19:54 - Vector commitment: Pedersen+IPA (Inner Product Argument)
23:27 - Pedersen commitment
24:52 - So how good are they really?
26:18 - The verkle multiproof
27:08 - Verkle proof cost
33:15 - Tree structure
35:10 - Key structure
38:36 - Summary
39-38 - Q&A
40:10 - Why do you need a verkle trie in the first place? Why can’t you have the commitment of the entire state?
41:45 - What data do you need to recalculate the root of the Verkle trie?
42:52 - What is the difference between the Account-level vs storage-slot-level expiry?
43:49 - What are bulletproof commitments? Why are Kate commitments preferred over bulletproof commitments for the Verkle tree?
44:25 - Setting storage slot to zero, is it related to verkle tree or state expiry?
45:20 - Source for verifying
47:02 - How feasible is it to verify a vector commitment inside an EVM transaction?
48:25 - Timeline for the EIP and discussion for upgrade inclusion
50:43 - Risk to the transition to the Verkle tree? How new are these crypto primitives that the verkle tree requires? Are they time-tested enough?
52:25 - Is there a possibility that there is too much reliance on the underlying Trie structure of Ethereum and we may get to a point where we try to make the trie upgrade to Verkle trie?
54:21 - Any other risks
54:58: Is 1.5 MB witness acceptable for 15 sec block time?
Resources
-------------------
Slides - https://docs.google.com/presentation/d/1OYZnlXUSWBPWAb15nybzD6u3Sj4ZAV3chQ-EZB-Nrwk/edit#slide=id.p1
Proto EIP- https://notes.ethereum.org/@vbuterin/verkle_tree_eip
Verkle Trie EIP-Calculator - https://docs.google.com/spreadsheets/d/1740XUDJ89aSRE-4HBD44brjGake_MRAqC4YF7YcEScE/edit?usp=sharing
Proposed Verkle tree scheme for Ethereum state - https://ethereum-magicians.org/t/proposed-verkle-tree-scheme-for-ethereum-state/5805
Verkle trie for Eth1 state - https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html
Ethereum Statelessness Roadmap - https://notes.ethereum.org/Yn_mwNa2SeeQHnKsRgekKg
Why stateless - https://dankradfeist.de/ethereum/2021/02/14/why-stateless.html
Inner product arguments - https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html
Verkle trees - https://vitalik.ca/files/misc_files/verkle.pdf
PCS multiproofs - https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
Proposed scheme for encoding Ethereum state into a Verkle tree - https://www.reddit.com/r/ethereum/comments/nve036/ethmag_proposed_scheme_for_encoding_ethereum/
Verkle Trees - Impact study on existing smart contracts (Draft) - https://docs.google.com/document/d/1s3qqzbkQFPcNvhzKPdnxg3MlFbv0YjK1z02SxRtdMs8/edit#heading=h.5izm3ka6fxpk
PEEPanEIP-3102: Binary trie structure & EIP-2584: Trie format transition with overlay trees with Guillaume Ballet - https://youtu.be/TrvKN2kZHQA
Follow PEEPanEIP earlier episodes at https://www.youtube.com/playlist?list=PL4cwHXAawZxqu0PKKyMzG_3BJV_xZTi1F
Follow at Twitter
-----------------------------------------------
Dankrad Feist @dankrad | Matt Garnett @lightclients | Pooja Ranjan @poojaranjan19
Check out upcoming EIPs in Peep an EIP series at https://github.com/ethereum-cat-herders/PM/projects/2
Contact Ethereum Cat Herders
---------------------------------------------------
Discord: https://discord.io/ethereumcatherders
Twitter: https://twitter.com/EthCatHerders
Medium: https://medium.com/ethereum-cat-herders
GitHub: https://github.com/ethereum-cat-herde...
Email: support@ethereumcatherders.com
Website: https://www.ethereumcatherders.com/
A
In
continuation
of
our
journey
to
learn
ethereum
through
this
educational
video
series,
where
we
talk
about
eip's
upcoming
features
and
important
concepts,
here
we
are
with
one
of
the
latest
research
topics:
vocal
trees,
welcome
to
another
episode
of
people,
I'm
pooja
ranjan
and
with
me
we
are
william
shaw
lifeline.
As
per
the
proto-eap
of
vocal
tree.
It
tries
to
solve
a
key
problem
standing
on
the
way
of
ethereum
being
stateless
client
friendly.
A
Its
implementation
will
be
the
first
step
in
a
multi-phase
transition
to
ethereum
exclusively
relying
on
verbal
trees
to
store
execution
state
to
talk
about
worker
trees
we
are
joined
by
dan
cradfies
dan
grid
is
a
researcher
at
ethereum
foundation
and
has
documented
multiple
resources
on
the
topic.
Welcome
dan
crowd,
thanks
for
joining
us
on
the
show.
B
A
B
D
B
Since
then,
I've
been
working
on
everything
like
mostly
things
that
can
concern
eth2,
the
proof
of
custody,
the
data,
availability
checks
and
and
other
things.
So
this
was
kind
of
the
first
time
earlier
this
year
that
I
started.
It
started
with
a
discussion
with
guillaume
from
the
guest
research
team
that
I
came
to
the
conclusion
that
I
should
try
to
see
if
vocal
vocal
tries
would
help
with
with
each
one
state
and
yeah.
B
B
So
earlier
this
year
I
wrote
a
blog
post
about
this,
where
I
presented
the
case
and
why
we
we
want.
We
really
do
want
statelessness
first,
but
that
the
best
paradigm
is
is
weak.
Statelessness
and
the
idea
behind
this
is
that
the
state
is
not
required
to
be
a
fully
validating
node.
That's
a
definition
of
statelessness.
So,
for
example,
these
two
validators
will
not
need
this.
B
It's
it's
to
some
to
a
chain
that
contains
an
in
irregular
state
transition,
and
in
that
case
they
should
not
follow
it,
and
this
is
so
far
not
possible,
but
it
will
actually
be
easily
possible
once
we
have
statelessness,
because
every
block
in
itself
is
is
simply
valid
or
not.
You
do
not
need
any
other
information
to
validate
whether
a
block
contains
a
valid
state
transition,
and
so
the
block
itself
is
the
fault.
Proof
is
which
is
basically,
I
would
say,
the
most
elegant,
a
solution
to
this
problem.
B
What
weak
means
is
that
block
builders,
slash
proposers,
so
I
mean
I'm
doing
this
like
either
or
here.
Well,
we
don't
know
yet
exactly
exactly
how
the
future
is
going
to
look
like,
but
someone
has
to
compose
a
block
like
basically
batch
transactions
together
and
compute.
The
new
state
route
and
whoever
that
is,
will
actually
still
need
the
state,
and
we
basically
say
it
is
fine
like
to
have
these
higher
requirements.
B
For
for
quite
a
few
reasons,
one
of
them
is
that
very
likely.
This
role
will
anyway
go
to
people
who
are
more
involved
in
extracting
mav
and
so
on.
So
it
seems
like
right
now
that
everything
is
going
to
that
direction
anyway,
but
also
from
a
practical
perspective.
It's
actually
not
that
bad,
because
it's
it
is
still
roughly
what
an
ethereum
full
node
needs
now.
So,
like
we're
not
going
crazy
here,
it's
not
gonna,
be
like.
B
Suddenly,
you
need
a
huge,
a
huge
computer
to
do
this,
that
you
can
only
get
a
data
center,
it's
just
slightly
more
than
what
you
need
to
run
a
normal
full
node
that
does
not
have
all
the
state.
Of
course
you
need
enough
space
to
solve
state
and
one
of
the
nice
things
that
this
also
solves
is
that
the
the
huge
discussion
we
had
last
year
around
the
dynamic
state
access
is
not
going
to
be
a
problem,
because
the
one
who
composes
the
blocks
actually
has
the
full
state.
B
But
if
we
just
try
to
add
all
the
witnesses
to
a
block
I'll
come
to
the
computation
of
these
numbers
later,
actually
it's
a
little
bit
worse
right
now,
but
we're
going
to
change
it
with
an
elp
with
hexary
merkel.
Trees
would
be
up
to
47
megabytes
using
current,
currently
the
max
30
30
million
gas
block.
B
That
is
huge,
like
that.
That's
really
that
would
be
a
massive
problem
if
we
did
just
switch
to
a
simple
binary
merkle
tree,
which
is
basically
the
the
best
possible
alternative,
we
we
had
previously
would
still
be
eight
megabytes
yeah,
it's
still
pretty
big,
so
it's
not
very
practical
to
do
either
of
these.
B
B
So
that's
where
the
v
comes
from
that
that's
the
only
thing
that's
changed
about
it,
so
it's
basically
a
tree
that
works
similar
to
merkle
trees,
but
the
commitments
will
be
vector
commitments
instead
of
hashes,
and
I
will
come
very
soon
to
what
a
vector
commitment
is
and
a
try
is
actually
simply
a
special
kind
of
tree.
It's
a
composition
of
the
word
stroke
tree
and
retrieval,
and
it's
basically
just
each
node
in
the
tree
represents
a
prefect
prefix
of
key.
So
don't
be
confused.
B
Okay,
so
to
illustrate
how
this
works,
I've
drawn
here,
a
merkle
tree
that
commits
to
16
leaves
at
the
bottom.
You
see
the
leaves
with
index,
I
made
them
binary
indices
and
because
that's
much
more
clear
in
the
merkle
tree
and
the
idea
is
always
each
node-
is
simply
the
hash
of
the
of
the
two
child
nodes.
So
it's
a
binary
mercury.
B
So
this
inner
node
zero
will
be
the
hash
of
inner
0,
0
and
inner
0
1
and
analogous
for
all
the
other
nodes
in
this
mercury
and
the
cool
thing
about
merkel.
Trees
is
that
we
can
compute
marker
proofs.
So
let's
say
we
have
this
leaf.
0
1
1
0,
and
we
want
to
prove
that
this
is
part
of
this
merkle
tree.
B
Then
what
we
have
to
do
is
simply
enable
the
verifier
to
compute
all
the
hashes
on
the
path
and
that's
quite
easy.
We
just
always
give
the
sibling.
So
if
we
give
this
direct
sibling
of
our
green
leaf,
that
we
want
to
prove
that's
zero
one
one
one,
then
we
can
compute
the
inner
node
zero
one
one
and
now
we
add
another
sibling
here-
is
inner
0,
1
0
and
together
with
these
two,
we
can
again
compute
the
inner
node,
0,
1
and
so
on.
B
So
now
what
happens
if
we
change
the
width
of
a
merkle
tree
so
to
illustrate?
I
have
drawn
here
a
merkle
tree
of
with
four
instead
of
the
two
previously
so
as
before.
Each
note
is
the
hash
of
all
the
children.
So
now
it's
always
four
children.
So,
let's
see
what
happens
if
we
want
to
compute
a
proof.
So
we
have
this
leaf.
0,
1,
1,
0
that
we
want
to
prove
as
part
of
the
smoker
tree.
B
And
now
you
see
where
the
problem
is,
we
have
increased
the
width.
Previously
we
needed
4,
we
have,
we
have
the
same
number
of
leaves
right
still,
16
leaves,
but
but
instead
of
having
to
provide
four
hashes
in
order
to
give
the
proof,
we
certainly
now
have
to
provide
six,
so
it
actually
becomes
strictly
worse,
and
so
this
is
annoying.
B
Basically,
if
you
increase
the
width
like,
then
you
need
more,
you
have
a
longer
proof,
and
this
is
exactly
what
happened
in
ethereum,
because
it
was
chosen
to
have
a
hexary
trees
which
is
with
16,
so
the
proofs
are
actually
very,
very
big
for
that
reason,
which
is
very
unfortunate
so
yeah.
This
is
a
summary
of
that.
B
The
problem
is,
you
need
all
the
settings
so
now
we
can
ask
the
quest
question:
what
if
we
had
a
scheme
where
we
could
prove
this
membership
more
efficiently
than
by
providing
all
the
settings
so
to
like
get
rid
of
this
problem
here,
the
problem
is
really
you
have
to
provide
like
all
these
siblings.
That
makes
it
very
large,
and
this
is
where
vector
commitments
come
in,
so
you
have.
We
have
some
vector,
like
think
of
x,
one
x,
two
and
so
on.
As
some
sort
of
values
like
say.
B
Probably
each
like
32
byte
value
is
a
very
typical
thing
and
you
can
com
compute.
The
commitment
c
of
to
all
of
these
values
and
an
opening
is
a
proof
that
some
x
I,
for
a
certain
index,
has
a
certain
value.
So
this
opening
will
be
another
another
binary
string
of
some
sort
and
with
the
property
that
when
I
as
a
as
a
verifier,
receive
this
opening,
I
know
that
x
I
equals
b,
and
so
this
v
has
been
provided
by
the
by
the
prover
and
and
as
well
as
this
opening
and
together.
B
So
in
this
definition
we
did
not
say
anything
about
the
size.
So
actually
a
merkle
tree
itself
is
a
vector
commitment
like
a
vertical
merkle
tree.
Has
this
property
we
did
earlier
c.
We
could
commit
to
a
vector
of
length
16
in
our
case,
and
we
could
compute
a
proof
that
a
certain
index
had
a
certain
value
and
the
proof
size
was
the
log
two
of
n,
where
n
is
the
length
of
the
vector.
B
One
example
I'm
going
to
give
here
is
that
I
I
have
like
also
give
some
give
some
presentation
in
the
past.
So
if
you
want
to
look
it
up,
I
introduced
those
before
I
also
wrote
a
blog
post
about
it,
but
it's
a
it's
actually
a
polynomial
commitment,
that's
much
more
powerful
than
just
a
vector
commitment,
but
you
can
use
it
as
a
vector
commitment
as
well,
and
just
the
properties
are
that
the
commitment
will
be
one
group
element.
B
So
if
we,
for
example,
use
bls
12
381,
which
is
the
curve
we're
going
to
use
in
eth2
for
most
things,
then
it
will
be
48
bytes
to
computer
commitment.
So
that's
like
slightly
larger
than
a
hash,
but
not
much,
and
the
proof
size
like
if
you
reveal
any
element
of
that
vector,
is
also
going
to
be
48
bytes
and
now.
This
is
interesting
because
it
doesn't
matter
how
many
elements
the
vector
has.
B
A
B
What
happens
when
we
open
this?
So
we
again
we
want
to
open
this
leaf.
We
have
to
provide
this
inner
inner
node
and
the
opening,
and
so
there's
open
of
three.
I
just
wrote
the
index
and
in
reality
there
are
more
things
you
need
to
compute
this
opening
than
just
the
index.
You
always
need
the
full
vector
as
well,
but
but
it's
basically,
the
the
verifier
will
only
see
this
opening.
B
Then
they
can
verify
aha,
this
leaf
as
part
of
this
node,
and
then
they
have
another
opening
that
will
show
that
this
node
is
part
of
the
route.
By
the
way.
One
slightly
thing:
that's
a
bit
different
than
compared
to
merkle
trees-
is
that
this
opening
itself
will
not
be
enough
to
just
compute
the
the
inner
node.
So
so
in
the
in
the
work
in
the
marker
proof,
once
you
have
the
siblings,
they
are
actually
sufficient
to
just
completely
compute
the
node
and
you
don't
need
to
provide
the
node
itself.
B
This
is
not
the
case
anymore,
so
this
changes
a
bit
and
you
actually
have
to
provide
the
inner
nodes
themselves,
but
you
don't
have
to
provide
the
siblings
anymore.
You
just
provide
the
openings
okay,
so
now
we
are
down
to
three
elements,
actually
in
almost
all
cases
that
we're
interested
in
the
commitments
will
be
additive,
and
that
means
that
you
can
do
certain
things
with
the
commitments
and
the
proofs
which
are
very
nice,
and
what
happens
is
that
all
the
openings
can
be
compressed
together
in
a
single
one.
B
B
Yeah,
so
that's
illustrated
here,
so
that's
basically
the
inner
node
and
then
the
opening
for
everything
and
just
a
quick
illustration
to
also
come
to
the
try
part
of
the
vertical
try.
So
that's
basically
a
try
means
that
that
whenever
you
go
down
in
the
tree,
you
basically
follow
the
prefix
of
the
key.
So
here
are
on
the
left.
You
see
all
the
keys
that
start
with
the
prefix
zero
zero,
so
they
will
be
summarized
in
a
node.
B
D
B
B
I'm
now
going
to
become
a
little
bit
more
concrete,
I'm
going
to
talk
about
what
we
actually
want
to
do
for
for
eth
one
state
and
the
the
vector
commitment
we
want
to
use
is
called
the
paterson
peterson
commitment
it.
You
might
have
come
across
it
before
it's
very
popular
for
inside
snacks,
for
example,
because
it's
very
efficient
to
verify
much
more
efficient
than
hashes
it's.
It
has
some
slight
disadvantages
compared
to
the
kcd
commitments.
B
When
you
want
to
open
only
a
single
one
to
open
a
pay-doesn't
commitment,
you
need
something:
that's
called
an
inner
product
argument
and
this
part
I
will
not
go
into
details
about,
and
I
can
refer
you
to
some
resources.
If
you
want
to
read
about
it,
I
will
also
have
a
link
later,
but
I
will
explain
what
appears
in
commitment
is
and
the
advantages
why
we
want
to
use.
This
is
that
we
don't
need
pairing,
friendly
groups
and
and
pairing
friendly
groups.
That,
like
are
the
main
reason
why
we
have.
B
We
have
such
large
group
elements
for,
for
example,
for
bls
12
381,
it's
48
bytes,
but
actually,
if
you
don't
need
pairings,
then
then
you
can
use
smaller
groups
and
they
only
need
32
bytes.
You
don't
need
a
trusted
setup
which
is
really
nice
and
I
think,
is
a
great
advantage
if
you're
dealing
with
something
as
delicate
as
state,
where
you
really
want
to
be
sure
that
that
everything
is
sound,
then
another
great
advantage
is
that
if
you
do
it
in
a
curve,
that's
well
aligned
and
with
with
your
curve.
B
Basically,
if
it
fits
into
another
curve,
where
you
can
do
snags,
then
you
can
do
everything
very
efficiently
inside
a
snark,
whereas
that's
not
the
case
for
hash
functions
like
computing.
A
sha-256
hash
in
a
snark
is
a
huge
effort,
it's
very
very
difficult
because
tens
of
thousands
of
constraints
typically
so
that
you
don't
want
to
do
that,
but
peterson
commitments
with
a
curve
that
fits
inside
bls
club
381
in
our
case
is
very
efficient,
and
so
this
makes
the
future
proof.
B
So
in
the
future,
once
that
becomes
efficient
enough,
we
can
basically
add
witness
compression
where
we
further
compress
down
our
witnesses
to
a
much
much
smaller
size
and
make
them
very
efficient
to
verify.
Actually,
potentially
we
can
do
that
now.
It
just
has
a
bit
more
latency
like
it
might
take,
maybe
like
a
few
minutes
or
hours
until
this
can
be
added
but
but
yeah,
so
so
that
it's
very
possible
now
to
be
honest,
and
it
also
enables
use
of
these
in
zk
roll
ups.
B
The
only
disadvantage
of
this
is
that
compared
to
kcg
commitments,
it's
not
as
efficient
if
you
just
want
to
prove
a
single
witness,
but
this
is
a
very
very
rare
case.
Like
I
don't
think
yeah
I
mean
even
a
transaction
proof
would
at
least
use
four
four
openings
and
already
then
it's
like
not
that
not
really
much
worse
than
kcg
commitments.
B
Cool,
so
how
do
peterson
commitments
work?
We
have
some
elliptic
elliptic
curve
g
and
we
have
some
generators
d1
g2
up
to
gn.
So
that's
the
the
length
of
num
of
these
generators
has
to
be
the
same
as
the
length
of
the
vector
that
you
want
to
commit
to,
and
the
important
thing
is
that
you
want
that
that
the
relative,
discrete
logarithm
between
these
generators
is
not
known.
So
you
don't.
B
You
don't
need
to
trust
anyone,
and
if
you
want
to
commit
to
a
vector,
x1,
x2
and
so
on
or
field
elements,
then
you
simply
multiply
each
of
them
by
their
respective
generator
and
take
the
sum,
so
it's
c
equals
x1
times,
d1
plus
x2
times
g2
and
so
on,
so
very
elegant
and
very
simple
and
yeah.
Here's
my
link
to
my
blog
post.
B
If
you
want
to
read
about
how
how
to
open
these
using
inner
product
arguments
yeah
so
now,
this
is
basically
starting
to
compare
like
how
good
can
we
get
with
these
vertical
trees.
So
this
is
based
on
on
this
30
byte,
32
byte
group
elements,
and
so
with
the
same
comparison
I
had
earlier
here,
I
have
the
numbers
as
well,
so
this
was
based
on
the
new
proposed
gas
cost
per
state
axis
of
1
900.
B
The
current
gas
limit
is
30
m
for
like
completely
full
eip159
blocks,
and
so
we
have
about
15
000
state
accesses,
so
unfortunately
with
hexary
merkle
trees
at
the
moment
that
would
generate
47
megabytes
of
witnesses
in
the
worst
case.
So
these
are
all
like
worst
case
number
binary,
merkle
trees
are
8
megabytes
and
if
we
use
with
256
vocal
trees,
then
we
can
get
that
down
to
1.5
megabytes,
which
is
a
manageable
number
for,
like
the
absolute
worst
case
blocks.
B
B
Yeah
so
quickly
to
talk
about.
I'm
not
I'm
actually
not
gonna
go
into
the
math
here,
but
I
wanted
to
to
reference
these.
I
I
wrote
a
blog
post
about
these
as
well.
So
if
you
want
to
know
how
to
how
to
open
all
these
commitments
and
combine
them,
then
then
read
this
blog
post
as
all
the
math
is
in
there.
B
B
Cool,
so
one
question
that
I
haven't
gone
into
is
is
about
the
the
cost
in
terms
of
computation,
and
so
so
far
we've
only
talked
about
witness
sizes.
This
is
actually
this
is.
This
is
the
major
reason
why
we
really
want
worker
trees?
There
would
be
other
polynomial
commitments,
as
you
know,
like,
for
example,
kcg
commitments
can
get
our
witnesses
down
to
constant
size.
If
we
wanted
to.
However,
their
problem
is
that
the
computation
is
insane
and
unfortunately
not
manageable,
so
I'm
going
a
bit
into
the
costs.
B
So
all
these
numbers
here
are
projections
from
I
mean
I,
I
know
that
we
can
get
the
basic
operations
down
to
these
numbers,
but
current
implementations
are
are
not
there
yet
so
see
these
as
projections
rather
than
about
then
benchmarks
of
what
we
have
implemented
right
now.
So
there
are
two
kinds
of
operations:
they're
field
operations
which
basically
always
refers
to
additions
and
multiplications
and
prime
fields.
Well,
the
interesting
part
is
multiplications.
B
Additions
are
pretty
much
trivial
and
the
multiplication
cost
in
a
prime
field
of
size
about
32
bytes
is
about
30
nanoseconds
on,
like
modern
hardware
and
the
other,
the
other
type
of
operations
we
have
are
group
operations,
and
these
are
additions
and
scalar
multiplications
in
an
elliptic
curve,
and
specifically,
we
are
talking
about
bender's
net.
This
is
a
highly
optimized
elliptic
curve
where
you
have
a
glv
endomorphism,
so
that
some
things
are
a
bit
faster
and
the
plane
scalar
multiplication
costs
about
40
microseconds.
B
So
this
is
always
like.
So
you
got
to
be
really
careful
with
these
numbers,
because
there's
a
factor
of
1000
between
these
right,
like
confusing,
microseconds
and
nanoseconds,
is
really
not
acceptable.
It's
a
huge
difference.
So
whenever
we
can
like
field
operations
are
basically
extremely
insanely.
Cheap
and
group
operations
are
a
lot
more
expensive.
B
The
good
thing
is
that
in
many
cases
we
can
reduce
these,
so
there
are
so
called
fixed
base,
multiplications,
where,
if
you
already
know
beforehand
what
your,
what
your
base
is
going
to
be
so,
for
example,
for
betas
and
commitments,
we
have
these
this
generator
sg1
g2.
So
we
already
know
them.
So
if
we
know
that
we're
going
to
do
a
lot
of
multiplications
with
them,
we
can
do
a
pre-compute,
and
then
we
can
get
that
down
to
about
five
microseconds
and
the
other
thing
is.
We
can
do
multiscalar
multiplications.
B
If
we
have
like
a
lot
like
a
combin,
linear
combination
of
a
lot
of
scalars
and
a
lot
of
group
elements,
then
we
can
also
accelerate
it
and
it
actually
becomes
faster
as
sorry
not
as
time
increases,
but
as
the
number
of
elements
increases.
So
that's
all
also
really
nice
and
as
a
comparison
like
a
very
rough
ballpark,
I
like
a
hash
costs
about
one
microseconds,
also
to
compute.
B
Okay,
so
let's
talk
about
the
the
cost
and
practice,
so
the
prover,
the
main
operation
that
they
need
to
do,
is
per
opening
so
for
each
vector
commitment
opening
they
will
need
to
about
to
do
about
four
times.
Two
five
six,
so
two
five
x
is
the
width
so
for
each
sibling.
Essentially
they
have
to
do
about
four
field
operations.
B
Operations
actually
mean
multiplications
here,
so
that's
about
30
microseconds.
So
each
of
them
is
10,
30,
nanoseconds
and
then
times
1
000.,
so
for
5
000
proofs,
which
will
involve
opening
about
25
000
vector
commitments,
because
for
each
proof
you
need
to
like
go
through
the
whole
tree
right,
so
we're
about
at
about
25
000
openings
that
would
be
750
milliseconds.
So
that's
a
fairly
acceptable
cost
that
only
the
prover
needs
to
do
once
for
every
block
so
like
it's.
B
The
verifier,
the
main
cost
in
the
multi-proof
scheme
is
a
multiscalar
multiplication
and
the
size
of
that
will
be
determined
by
the
number
of
commitments
that
have
to
be
opened,
and
so
that's
a
nice
thing.
This
is
less
the
number
of
openings.
So
basically,
maybe
we
go
back
to
to
the
worker
proof
right,
so
here
I'm
opening
two
commitments
in
seo:
one
and
the
root
for
each.
I
have
to
open
these
two,
but
let's
say
I
also
wanted
to
prove
the
leaf
zero
one:
zero,
zero!
B
That's
actually
a
sibling
of
zero
one,
one
zero!
This
does
this
is
another
opening.
So
I
have
to
open
this
commitment
in
a
zero
one
now
at
two
places,
but
it
does
not
open
a
new
commitment
and
this
the
marginal
cost
for
this
is
very,
very
low.
So
that's
nice,
so
that
okay,
so
so
that's
why
it's
less
like.
I
estimate
here
roughly
like
15
000
commitments
that
you
need
to
open,
so
the
multiscale
multiplication
would
be
of
size,
15
000..
B
This
number
is
the
one,
I'm
least
certain
about.
I
estimate
that
once
we
have
well
optimized
implementations
for
those,
this
could
be
in
the
range
of
50
to
150
milliseconds,
and
a
very
nice
thing
here
is
the
marginal
cost
of
opening.
Another
position
in
the
same
commitment
is
like
super
low.
We're
talking
about
nanoseconds,
really
like
actually
less
than
a
hash,
potentially.
B
So
that's
where
we
come
to
the
tree
structure
that
we
have
we
are
suggesting
now,
so
the
idea
is
that
what
we
want
in
our
design
goals
is
that
we
want
to
make
access
to
neighboring
code,
chunks
and
storage
slots
very
cheap.
So,
like
one
when
an
act
when
a
contract
is
executed,
you
expect
that
many
of
the
much
of
the
code
that
you
access
is
like
actually
very
close
to
to
each
other.
B
So
you
want
that
not
each
of
these
represents
a
random
state
axis,
so
we
want
to
make
that
cheap,
but
we
have
a
kind
of
conflicting
goal
that
it
would
be
nice
to
distribute
all
the
state
as
evenly
as
possible
in
in
the
tree
because
then
stuff
like
state,
so
it
becomes
much
easier.
You
can
do
it
just
by
like
prefixes
and
stuff
so
that
that
would
be
nice
as
well
further.
We
want
that
the
scheme
is
fast
in
plain
text,
so
we
want
that
opening
neighboring
chunks.
B
Not
to
involve
opening
a
new
commitment
and
we
want
it
to
be
fast
and
snarks,
and
that
mainly
means
we
want
no
hashing.
We
only
want
fiddles
and
commitments
because
they
are
fast
and
the
last
design
goal
is.
It
should
also
be
forward
compatible
because
we
expect
that
in
to
ten
years
or
sometime,
we
want
to
upgrade
to
a
post
quantum
scheme
and
and
then
we
should
only
yeah.
We
only
want
to
work
with
a
pure
key
value
store
and
not
do
something
complicated
due
to
the
scheme
that
we're
using
now.
B
So,
in
order
to
achieve
this,
we
basically
do
something
with
the
key,
and
the
idea
is
this:
we
have.
We
have
I'll
only
talk
about
storage.
Everything
else
is
kind
of
similar,
but
this
gives
you
the
idea
of
how
this
is
going
to
work.
So
we
have
a
contract
address
and
a
storage
location
that
we
want
to
access.
Each
of
these
are
basically
32
bytes
and
what
we
compute
is
what
I
call
a
stem,
and
that
is
a
pedestal.
Commitment
of
this
contract
address
and
the
storage
location
minus
the
last
byte.
B
Think
of
the
spade,
as
a
commitment
or
just
as
a
hash
function,
and
the
reason
why
we're
doing
pay
doesn't
he
is
once
again
so
that
in
the
future,
snarks
can
do
this
also
very
efficiently,
but
ignore
that
and
think
of
it
as
a
hash.
If
you,
if
that's
easier
for
you
and
then
this
this
last
byte
of
the
storage
location,
I'm
using
python
notation
here,
this
minus
one
is
the
last
byte
we
call
the
suffix,
and
so
that's
not
including
the
stem.
B
Will
map
close
to
each
other
and
so
the
way
we
do
that
is
they
only
change
the
last
byte
and
then
this
is
how
we
com
compute
the
tree
for
this.
So
basically,
the
stem
will
feed
into
a
vocal
tri,
pure
vertical
tri
structure
and
then
for
the
suffix
we
compute
the
so-called
suffix
tree.
So
basically,
once
the
the
vertical
triangle
go
up
to
a
position
where
there's
no
other
stem
with
the
same
initial,
and
at
that
point
there's
this
extension
node.
That
is
a
peterson
commitment
to
one
stem
and
two
commitments.
B
B
We
have
to
split
up
into
in
of
16
bytes
each,
and
that's
also
why
we
need
these
two
commitments
here
in
the
extension
node,
because
each
each
of
them
can
only
store
128
bytes,
but
we
have
a
total
of
256
bytes
that
have
the
same
256
values
that
have
the
same
stem
and
have
to
go
into
the
same
subject:
stream
and
yeah.
Here
you
can.
This
is
a
link
below
to
the
current
worker
tree
eip,
written
by
vitalik
and
me
that
implements
this.
B
Cool
so
yeah
to
summarize
the
main
advantage
of
worker
vertical
trees.
Is
it's
a
huge
reduction
in
the
witness
sizes
so
we're
talking
about
five
times
versus
the
binary
mercuries,
which
is
so
far
the
best
alternative
we
know
of
and
more
than
30
times
compared
to
hexate?
So
that's
yeah,
that's
huge!
We
need
to
change.
Definitely
and
hacks.
Routines
are
just
terrible.
B
A
D
B
B
The
problem
is
that
for
all
vector
commitments
we
know,
and
we
actually
now
think
that's
a
fundamental
property.
If
the
proof
is
constant
size,
it
means
you
need
to
do
something
to
compute
the
proof
itself.
You
need
to
do
something
that
involves
everything.
That's
in
the
vector
commitment
right
so
like
say
you
take
a
kcg
commitment
of
the
full
state
which
has
like
a
billion
elements.
Then
computing.
The
proof
needs
to
do
something.
With
those
billion
elements
and
yeah.
You
can
see
that
doesn't
scale
like
it's,
it
doesn't
work.
So
it's
it's.
B
B
D
B
Oh
updating
no
like,
if
you
have
a
state
access.
Basically
you
need
yeah.
So,
like
you,
you
need
to.
You
can
have
the
updated
in
a
similar
way
to
a
merkle
tree.
So
you
need
all
the
intermediate
commitments
that
go
to
to
your
leaf,
that
you've
changed,
updated
and
and
then
you
can
compute
the
update
from
there.
So.
B
A
B
A
B
No,
actually,
oh,
no!
No!
No!
So
we
originally
started
with
cutting
commitments,
so
kcg
or
cardiac
commitments.
I
introduced
them
earlier,
but
we
actually,
we
have
now
pivoted
towards
pedestrian,
which
is
bulletproof
essentially
like
that's
just
another
name
yeah.
So
we
are
using
bulletproof
commitments
because
we
we
have
figured
out
that
they
are
pretty
much
better
in
every
way
for
our
application,
specifically.
C
B
That
is
as
related
to
expiry,
because,
basically,
if
you
want
to
expire
state,
you
need
to
be
able
to
tell
whether
a
whether
a
slot
has
has
existed
and
been
written
to
zero
or
has
never
existed
like.
Basically,
because
you
need
to
know
whether
the
slot
is
part
of
the
current
state
or
whether
you
need
to
look
up
some
old
state.
And
if
you
just
deleted
it
in
the
current
state,
then
you
would
lose
that
information
yeah.
C
Great
thanks
also,
I
really
appreciated
having
the
source
in
the
vertical
tree
right
up
like
understanding
the
verifier.
That
way,
it
was
really
helpful
if,
if
there's
any
way
to
add
the
the
source
for
proving
a
commitment
or
for
verifying,
rather
that
would
be
like
helpful
as
well.
I
I
see
the
source
for
like
com,
you
know
proving
the
commitment,
but
I
had
I
didn't
find
the
source
for
for
verifying
it.
C
C
B
A
B
Good
question
so
so
we'll
need
to
add
op
codes
for
whatever
curve
we
are
using.
I
think
the
only
sensible
thing
is
to
have
that
native
and
dbm,
because
we
are
going
to
like
I
mean
every
client
needs
to
have
it
anyway
so
like.
Why
not
also
add
it
as
an
op
code.
I
think
then
it
would
be
very
easy
to
verify
it
like
once
you
have
the
basic
curve
operations
without
them.
I
don't
know.
I
suspect
it's
actually
possible
now
to
implement
this,
because
the
math
is
not
that
bad.
B
A
Thank
you.
So
my
next
question
is
related
to
the
process
and
the
timeline.
I
know
there
have
been
research
on
this
local
try
for
it
for
a
while,
so
and
there
is,
and
also
a
proto
eip
up
that
which
I
shared
the
other
day
when
you
think
we
can
have
a
formal
proposal
like
it
is
still
in
not
as
in
pull
request
for
the
local
trees
and
like
when
it
will
be
ready
for
climb
to
start
discussing
for
inclusion
and
future
upgrade.
B
Yeah,
I
probably
don't
want
to
give
a
firm
like
timeline
here,
because
I
haven't
discussed
this
with
everyone.
So
there's
a
team,
so
the
guillaume
ballet
from
from
geth
is
currently
working
on
this
I'd
say
there
has
been
a
bit
of
disruption
of
timelines
because
we
have
done
some
major
changes
in
terms
of
like
pivoting
from
kcg
to
pedestal
commitments,
for
example,
as
we
as
we
just
discussed.
B
So
I
think
we
kind
of
have
to
yeah
go
through
that
again
and
like
see
where
we
land.
I
don't
have
like
really
good
estimates
on
the
timelines
right
now
so,
but
there
is
a
team
already
on
it,
implementing
it.
I'm
of
about
five
people
or
so
so
I
expect
that,
hopefully
like
in
the
next
few
months
by
the
end
of
the
year,
we
should
have
good
prototypes
and
we
should
have
enough
to
like
put
that
into
an
eip
very
roughly.
B
Yes,
for
sure
yeah,
no,
I
mean
we're,
definitely
not
going
to
do
that
before
the
merge.
I
I
mean
ideally,
of
course
like
I'm.
I
I'm
very
adamant
that,
like
statelessness,
is
very
central
and
like
I
would
really
like
to
have
it
as
soon
as
possible
after
the
merge,
but
of
course
that
depends
on
all
the
implementation
and
everything.
So
I
can't
really
say
what
what
the
constraints
they
are.
A
D
I
just
had
a
like
more
general
question
of
what
are
the
risks?
Do
you
see
of
the
transition
to
the
verbal
try,
and
you
know
specifically,
one
question
is
like
how
new
are
these
crypto
primitives,
that
the
vertical
drive
require
and
are
they
things
that
we,
we
think
are
time
tested
enough
to
to
be
used
at
the
base
protocol.
D
B
So
it's
very
basic:
that's
nice!
We
are
suggesting
a
new
curve.
I
talked
to
cryptographers
and
they
said
that,
like
our
methods
of
generating
new
curves
are
very
reliable
and
like
there's
no
like
I,
I
would
definitely
want
to
have
it
vetted
more,
but
from
cryptographers
I've
talked
to.
They
didn't
tell
me
that
there's
any
concern
about
that.
B
So
I
would
say
I
I
don't
think
cryptographically.
There
are
major
concerns
anywhere,
I
think,
but
I
think
there
is
definitely
some
complexity,
for
example
in
the
multi-proof.
So
I
guess
that
that
that
would
need
yeah
quite
a
bit
of
work
to
be
really
sure
and
auditing
yeah,
but
I
would
say
not
not
from
not
on
the
basics,
like
the
basic
assumptions
are
very
sound.
D
There's
definitely
some
smart
contracts
that
verify
like
patricia
witnesses,
and
I
I
don't
know
for
sure,
but
I've
heard
some
people
talking
about
some
bridges
on
other
chains
that
do
have
logic
that
relies
on
right,
verifying
witnesses
and
so
again
like
I,
I
I
think
this
is
going
to
be
a
really
tricky
thing.
I
think
at
the
end
of
the
day,
we'll
be
able
to
upgrade,
but
it
is
going
to
be
a
hard
thing
to
convince
everyone
and
probably
needs
a
lot
of
lead
time
to
ensure
that
everything
is
upgraded.
B
Yeah
I
mean
my
expectation
is
that
for
most
of
these
projects,
they're
bridges
to
ethereum
are
probably
so
central
that
they
will
just
upgrade
them
and
do
whatever
hard
fork
they
need.
So
the
only
real
danger
I
see
is
any
smart
contract
that
does
state
verification.
I
I'm
not
sure
why
anyone
would
do
that,
but
yeah.
B
I
mean
there's,
the
question
is:
are
we
going
to
just
discover
better
commitments?
Why
are
we
doing
this
and
we're
like?
Oh
like
we
should
have
used
that?
I
think
it
seems
very
unlikely
at
this
point
like
we
are
investing
in
it,
but
I
haven't
seen
anything
on
the
horizon
at
the
moment
that
looks
like
it's
actually
even
close
to
being
competitive,
yeah.
D
B
B
B
All
the
edge
cases
here,
which
which
are,
of
course
like
what
would
you
like
how
you
can
exploit
the
lower
cost
for
accessing
accessing
data
in
the
same
suffix
and
stuff,
like
that,
I
I
have
done
some
some
components
like
I've
got
some
sheets
and
try
to
go
through
it.
The
thing
is,
of
course,
all
of
this
currently,
as
I
said,
they
aren't
benchmarks
they're.