►
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/challenges-of-parallelizability-under-ethereums-execution-model/
We highlight two challenges of parallel execution on Ethereum: 1. Historical data shows that data dependencies force us to execute a large portion of transactions serially. 2. If we assign incentives to scheduling decisions, this might introduce non-determinism that the system cannot tolerate. In this lightning talk, we present these two problems and outline some proposed solutions.
Note that this work was accepted for and presented at ICSE'22 (https://bit.ly/3HzPKZT)
Speaker(s): Péter Garamvölgyi
Track: Layer 1 Protocol
Keywords: parallel execution,optimistic concurrency control,deterministic scheduling
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
Get
up
early
and
come
to
this
talk,
so
my
name
is
Peter
and
I'm.
Gonna
talk
about
our
work
that
we
did
at
the
Shanghai
blockchain
Research
Institute,
and
what
we
did
was
we
investigated
how
hard
it
would
be
to
execute
transactions
in
Peril
on
the
evm?
As
you
might
know,
the
evm
is
designed
in
a
sequential
manner.
Usually
you
execute
all
transactions.
You
know
block
one
by
one,
so
the
question
is:
can
we
paralyzed
that?
Well,
we
found
what
I
want
to
talk
about.
A
Today
is
two
challenges
that
we
identified
and
the
first
of
those
is
transaction
dependencies,
you're,
probably
all
familiar
with
how
ethereum
Works.
Basically
we
have
a
global
share
state,
which
is
the
state
tree.
Theoretically,
a
transaction
could
access
any
point
any
entry
in
this
state
tree.
That
is
where
it
can
access
a
slot
or
not
that's
defined
by
the
contract
code.
A
So,
for
instance,
if
you
have
two
transactions
from
two
different
accounts
and
both
of
them
call
the
same
contracts
and
that's
contract,
reads
or
writes
the
same
entry,
then
these
transactions
will
have
a
conflict
or
a
dependency
on
ethereum.
This
is
not
a
problem.
Now
because
we
execute
transactions
sequentially,
but
if
you
paralyze
them,
then
this
will
become
a
problem
because
you
cannot
concurrently
execute
such
transactions.
So
we
did
some
evaluations.
Basically,
what
we
did
is
we
collected
some
storage
traces
for
a
few
hundred.
A
Thousands
of
blocks
from
you
know
historical
data
on
ethereum,
and
we
did
some
simulations
with
some
OCC
scheduler,
and
what
we
found
is
that
the
theoretical
maximum
speed
up
is
as
little
as
four
times
so,
even
if
you
have
eight
threads
or
16
threads,
at
least
on
the
VM
level,
if
you
don't
consider
storage,
you
cannot
do
much
much
better
than
four
times
and
that's
kind
of
an
underwhelming
result.
So
some
examples,
some
simple
examples
of
these
dependencies.
A
For
instance,
if
you
have
two
transactions
to
the
same
erc20
token,
if
they
send
from
the
same
senders
to
the
same
receiver,
then
they
will
conflict
on
the
balances
mapping
or
if
you
have
two
transactions,
swapping
tokens
on
uni
swap
swapping
the
same
token
pair,
then
both
of
them
will
modify
the
reserve
variables.
So
that's
also
another
kind
of
conflict,
or
if
two
transactions
are
minting
and
nft,
then,
for
instance,
they
can
conflict
on
total
Supply
if
the
contract
is
keeping
track
of
that.
We
identify
this,
and
this
is
an
issue.
A
A
Let's
say
we
take
the
last
byte
of
the
hash
of
the
sender
address,
so
two
transactions
from
different
senders
would
probably
with
a
higher
probability
they
would
modify
different
slots
in
the
contract,
and
the
second
idea
that
we
came
up
with
is
a
lazy
ad
op
code,
so
for
in
this
example,
we
have
a
very
simple
function:
that's
just
incrementing
a
counter,
but
when
you
compile
it
to
evm
byte
code,
what
you
have
is
a
storage
load
operation.
Then
you
do
something
with
that
value
and
you
store
it
back
so
to
concurrent
transactions.
A
We'll
have
a
conflict
on
this.
Like
concurrent
storage,
load,
storage
store
operations,
and
you
know
we
cannot
paralyze
them.
The
idea
here
is
to
maybe
introduce
a
new
kind
of
semantics
for
addition,
lazy,
ad
or
commutative
ad,
and
that
would
be
evaluated
lazily,
so
these
transactions
can
execute
in
Peril
and
then
we
basically
batch
those
two
updates
together
into
a
single
update
at
the
end
and
that
could
be
executed
at
the
end
of
the
block.
For
instance.
The
second
challenge
that
we
identified
is
that
of
determinism.
A
So,
as
you
might
know,
in
parallel
execution,
there's
a
you
know,
there's
a
lot
of
non-determinism
and
we
can
make
sure
that
two
transactions
have
the
same
result
or
two
executions,
but
there
are
other
types
of
non-determinism.
For
instance,
here
we
have
two
executions
of
three
times:
three
different
transactions
and
let's
say
transaction
two
depends
on
transaction
one.
A
So
in
this
case
on
node
a
one
and
two
are
executed
concurrently,
so
two
has
to
abort
and
be
re-executed,
because
there's
an
update
that
it
could
not
see
and
on
node
B
the
execute
is
sequentially,
so
no
transaction
two
can
commit
directly.
Our
idea
is
that
if
we
have
parallel
execution
at
some
point,
we
have
to
introduce
some
incentives,
because
if
you
can
trigger
some
aborts,
that
kind
of
opens
up
the
door
for
some
denial
of
service
attacks,
and
if
we
do
associate
some
incentives
with
aborts,
then
to
these
two
executions.
A
In
the
example,
they
will
yield
the
difference
final
state.
So
that
is
going
to
be
an
issue.
Two
nodes
will
diverge
so
for
this
we
kind
of
came
up
with
a
new
scheduling
framework
called
optimistic
concurrency
control
with
deterministic
aborts,
and
the
idea
is
very
simple.
Instead
of
deciding
these
abort
comment
decisions
during
runtime,
you
made
this
decision
prior
to
running
those
transactions
in
a
deterministic
way,
so
the
these
decisions
will
be
deterministically.
A
You
know
the
same
on
all
nodes
and
this
way,
even
if
you
attach
incentives
to
these
decisions,
the
final
states
that
different
nodes
will
arrive
on
will
be
the
same.
So
this
is
the
OCC
da
framework
just
to
summarize
kind
of
the
takeaway
from
the
stock.
So
it's
pretty
hard
to
get
parallelization
done
on
the
evm,
because
it
was
not
designed
with
this
in
mind,
but
I
think
it's
going
to
be
worth
it.
A
For
instance,
if
you
manage
to
scale
ethereum
on
layer,
1
or
layer
2
with
a
higher
transaction
transaction
load
per
execution
will
have
a
very
big
impact
on
the
overall
yeah
efficiency
of
the
system.
So,
if
you're
interested
in
this,
you
know
research,
Direction
I
would
encourage
you
to.
You
know
read
up
on
it
think
about
it
and
we
actually
have
a
publication
about
this
topic.
A
B
B
A
Yeah,
that's
a
good
question,
so
here
we
only
considered
con
contract
storage
conflicts,
but
actually
there
are
different
kind
of
conflicts.
You
know
another
part
of
the
state
trees,
the
account
with
the
nouns
and
the
balance,
so
yeah
simple
transfers
are
expected
to
be
much
easier
to
paralyze
and
even
with
contracts
with
access
lists.