►
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/improving-performance-of-provable-computations-using-rust/
We reimplemented the Cairo VM in Rust to increase its performance. We will show an MVP that is between 10 and 100 times faster than the previous Python implementation.
Executing a program with this VM outputs a trace which can later be used to generate a Proof of the program's execution. Combining Zero Knowledge Proofs with Rollups allow us to have scalability without compromising the security of blockchains.
Speaker(s): Herman Obst, Federica Sofía Moletta
Skill level: Intermediate
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: Virtual Machine,Zero Knowledge Proof,L2
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
Thanks
all
for
coming
in
today,
and
in
this
talk
we
are
going
to
be
talking
about
how
we
improve
the
performance
of
probability
computations
using
rust
and
specifically
how
we
implemented
the
carobm
using
rust.
So,
okay,
let's
go
first
I
want
to
give
a
little
worse
on
who
we
are.
We
around
the
class
Lambda
class
is
a
lesson
base
so
for
company
and
it's
in
the
industry
a
more
head
interiors
and
yes,
basically,
we
love
soybean
difficult
problems.
A
So
that's
really
cool,
because
the
verification
of
the
transaction
does
not
depend
on
only
one
computer
on
a
centralized
entity
but
on
every
computer
inside
the
network.
But
it
comes
with
a
downside,
and
the
downside
is
that
the
computation
capacity
of
the
network
depends
of
on
your
slowest
note.
So
we
have
in
a
situation
that
we
have
a
high
demand
of
running
transactions
and
our
computation
capacity
is
limited
by
our
slowest
low.
So
how
can
we
solve
this
problem?
A
Starnet
is
a
secret
roll
up
and
what
rollapse
allows
us
is
to
run
transactions
of
chain
then
make
a
batch
of
intersection
and
send
to
ethereum
the
update
State,
and
what
CK
adds
to
roll
up
is
that
we
can
run
the
construction
of
chain
generate
a
proof
of
the
Integrity
of
the
execution
of
the
transactions,
and
then
we
send
to
ethereum.
They
update
the
state
and
the
proof
of
the
computational
integrity.
A
So
then,
on
chain
the
proof
is
verified
by
a
verifier
and
that
verification
is
running.
All
the
computers
inside
ethereum
so
well,
and
the
coolest
thing
about
this
verification
is
that
the
verification
cost
of
the
proof
growth
logarithmically
with
respect
the
number
of
transactions
inside
the
batch.
So,
as
the
the
cost
of
verification
is
distributed
between
all
the
transactions,
including
the
batch,
as
we
add
more
transactions
in
the
in
the
batch,
the
cost
per
transaction,
the
average
cost
per
transactions
goes
to
zero.
A
So
yeah
here
is
a
slide.
That
I
was
supposed
to
to
say
that
because
of
verification
grows
logarithmically
and
with
respect
the
numbers
and
section
and
yeah
if
we
tend
to
Infinity,
if
you
take
this
one
extreme
and
we
tend
to
Infinity
the
number
of
transactions
inside
the
batch,
the
cost
the
average
cost
per
transactions
go
to
zero.
A
So,
okay,
we
say
that
in
stagnet
we
can
generate
a
proof
on
the
execution
of
our
transaction,
but
what
kind
of
proof?
Well,
it's
a
series
proof
and
specifically
a
stack
and
to
your
knowledge,
allows
us
to
prove
the
veracity
of
a
statement
without
rebuilding
anything
beyond
the
fact
that
the
statement,
the
statement
is
true
and
in
this
specific
case,
Stacks
allow
us
to
prove
their
computational
integrity
of
the
transaction
that
would
run
off
chain.
A
We
are
having
to
run
it
all
again,
so
this
is
kind
of
a
game
changer,
because
before
serial
knowledge,
the
only
way
we
had
to
to
prove
the
rest.
The
computation
Integrity
of
a
computation
was
to
run
that
computation
ourselves,
but
with
with
your
knowledge
and
stacks
now
and
untrusted
entity
can
run
transactions
a
generator
proof
on
the
Integrity
of
that
execution,
and
then
the
proof
have
to
be
verified,
and
we
can
be
sure
that
everything
is
okay.
A
So,
okay,
how
do
we
write
a
program
that
is
a
probable
meaning
that
its
execution
can
be
can
be
proven?
The
Integrity
of
execution
and
okay?
We
have
Cairo
and
Cairo
is
a
primary
language,
a
specific
design
to
doing
this.
When
we
we
write
a
program
in
Cairo,
it's
run
in
the
Caribbean
and
that
Cairo
VM
executes
a
program
and
also
generate
a
trace
of
the
execution,
and
that
Trace
is
then,
is
going
to
be
sent
to
approver
and
generate
the
start.
Proof,
and
that's
that's-
that
probe
is
going
to
be
verified
by
a
verifier.
B
Now,
let's
talk
about
about
how
the
Caribbean
works.
Well,
you
already
know
how
a
virtual
machine
works.
Basically,
you
write
your
source
code,
you
compile
it
and
then
you
use
the
virtual
machine
to
interpret
that
compile
code
and
execute
the
instructions.
But
what
sets
apart
this
current
Bureau
machine
is
that
it
also
generates
this
Trace
that
can
be
used
to
generate
the
proof.
B
A
B
Segments
consists
of
the
program
segment,
which
contains
the
code
of
the
program.
The
execution
segment,
which
gets
filled
up
as
the
VM
runs
the
built-in
segment
which
we'll
talk
about
later
and
the
user
segment,
which
contains
structures
defined
by
the
users
such
as
arrays
or
dictionaries.
Well,
let's
explain
a
bit
about
this
provocation
process.
The
first
step
is
to
assign
a
size
to
each
segment.
For
example,
the
segment
serial
has
five
elements,
so
it
has
size
5
and
then
we
will
use
the
sizes
to
assign
a
base
to
each
segment.
B
So,
for
example,
here
we
have
the
segment
the
address,
0
0,
the
base
of
the
segment
0
is
1
and
we
add
0
and
get
one
we'll
do
this
with
all
the
addresses
and
also
with
the
addresses
that
are
contained
inside
the
memory.
For
example,
you
see
here
that
we
have
two
zero
and
three
zero
and
they
both
relocate
to
nine
as
the
base
of
the
segment
two
and
segment
three
is
nine,
and
this
is
how
the
relocated
memory
looks
like
it's
a
set
of
continuous
addresses
with
elements.
B
But
now,
let's
talk
about
the
registers,
Cairo
has
three
general
purpose
registers.
The
first
one
is
the
program
counter
which
iterates
over
the
program
segments
and
points
to
the
next
instruction
to
be
executed.
Then
we
have
the
frame
pointer
and
allocation
pointer
in
execution
segment.
The
allocation
pointer
will
point
to
the
next
and
use
memory
cell,
while
the
frame
pointer
points
to
the
current
frame.
What
this
means
is
that
when
we
want
to
execute
a
chiro
function,
the
frame
pointer
takes
the
value
of
the
allocation
pointer
and
remains
constant.
B
While
the
allocation
pointer
keeps
increasing,
as
we
add
elements
into
memory,
and
when
we
exceed
this
function,
the
frame
pointer
will
change
its
value.
This
is
how
the
VM
operates.
This
is
the
main
execution
Loop.
We
first
get
the
next
instruction.
We
decoded
we
compute
the
operands.
Then
we
add
the
current
register
values
to
a
trace,
and
then
we
update
the
registers
so,
okay,
this
is
how
the
trace
looks
like
it
keeps
track
of
how
the
registers
change
for
the
execution
of
the
program,
and
it
also
goes
through
the
same
relocation
process
as
memory.
B
Well,
as
we
can
see,
the
size
of
this
Trace
will
depend
on
the
amount
of
steps
that
a
chirop
program
takes.
So
if
a
chiral
program
takes
a
lot
of
steps,
this
Trace
will
get
very
big
and
will
take
more
time
to
generate
the
proof.
So
sometimes
there
are
some
computations
which
are
expensive,
take
a
lot
of
steps,
but
maybe
the
information
provided
by
each
of
the
steps
is
not
that
relevant.
For
example,
if
we
want
to
compute
a
Pederson
hash,
this
will
take
many
many
steps.
B
So
in
order
to
solve
this,
what
we
have
is,
oh
sorry,
we
have
built-ins.
Built-Ins
are
low-level
optimizations
that
are
integrated
in
the
core
Loop
of
the
VM
and
they
allow
otherwise
expensive
computation
to
be
performed
more
efficiently.
And
while
each
of
these
segments
each
of
the
built-ins
have
a
segment
in
memory.
Okay,
but
where
do
they
come
into
play?
B
Well,
we
see
here
that
we
have
our
main
execution
Loop
and
we
have
this
the
GS
operands
added,
and
what
this
means
is
that
sometimes
we
might
want
to
compute
an
operand
and
we
can't
really
compute
it
directly
and
we'll
rely
on
some
deduction
rules.
Example:
here
we
have
the
Paterson
built-ins
Auto
reaction
wall.
What
it
does
is
it
takes
the
two
previous
values
in
memory
and
computes
the
patterns
and
hash
of
them.
B
This
rule
comes
into
play
when
the
address
of
the
operand
that
we
cannot
compute
belongs
to
the
built-in
segment
and
that
built-in
has
the
anal
to
the
action
rule.
So
what
does
what
this
allows
us
to
do
is,
for
example,
here
we
want
to
compute
the
hash
of
X
and
Y.
So
what
we
do
is
insert
X
and
y's
memory,
and
then
we
ask
for
the
next
memory
location.
As
we
haven't
inserted
anything
into
this
memory
location.
B
We
won't
be
able
to
compute
the
operand
and
we
will
fall
back
on
this
deduction
rule
that
will
be
the
one
Computing
the
hash,
so
we
computed
a
person
hash,
but
there
is
no
sign
of
the
computation
in
the
chiral
memory
or
the
steps
or
the
trace.
Another
feature
that
Cairo
offers
are
hints.
These
are
blocks
of
python
code
embedded
into
a
career
program
and
they
allow
a
python
context
to
access
the
BM,
State
and
modifier
also
access
local
carrier
variables
and
can
communicate
between
each
other
for
execution
Scopes.
B
What
we
see
on
screen
is
the
unlock
function
from
the
common
Library.
This
function
is
commonly
used
to
generate
arrays
and
what
it
does
is
it
creates
a
new
segment
and
it
inserts
it
into
memory,
so
we
can
use
it
from
Cairo.
We
mentioned
execution
skills.
These
Scopes
are
a
stack
of
dictionaries
that
can
hold
variables
that
are
created
inside
a
hands.
These
variables
are
not
seen
by
Carol
just
by
the
hands,
and
this
can
be
created
and
removed
inside
hints
and
multiple
hints
can
access
the
same
scope.
B
B
And
then
we
exit
the
scope
deleting
this
and
variable
well,
so
now,
let's
talk
about
how
we
implemented
hints
in
Cairo
RS,
that
is
our
implementation
of
the
VM.
Well,
first,
why
we
chose
rust.
We
chose
Frost
because
it
offers
very
good
performance
memory
safety
guarantees,
and
it
also
has
an
amazing
Community.
B
Well,
our
first
iteration
of
hints
entire
RS
was
basically
to
implement
Ros
functions
that
would
imitate
the
behavior
of
hands
and
match
these
blocks
of
python
code
to
our
sense,
for
example,
the
constants
we
see
here
are
the
blocks
of
python
code,
and
this
is
again
the
example
of
the
alac
function.
This
is
the
block
of
python
code,
and
this
is
how
we
replace
it
with
a
rust
native
function.
Well,
this
first
iteration
had
pros
and
cons
on
the
cross
side.
B
We
first
applied
this
to
the
common
Library,
so
if
a
common
Library
hand
were
to
change,
we
needed
to
change
our
implementation
in
order
to
keep
supporting
it,
and
it
also
wasn't
really
extensible
as
if
we
wanted
to
support
more
hints,
we'd
had
to
code
it
inside
our
BM.
So
as
we
wanted
to
support
user
defined
hints,
and
we
also
wanted
to
integrate
our
VM
with
the
current
python
infrastructure,
we
decided
to
go
with
the
next
iteration
that
consisted
of
integrating
python
with
RBM.
In
order
to
achieve
this,
we
used
the
create
Pi
u3.
B
It
is
a
creative,
provides
rust
bindings
for
Python
and
it
allowed
us
to
share
our
BM
state
with
the
python
context.
I
know
that
python
context
to
modify
RBM
and
also
allow
us
to
define
a
strict
interface
between
our
VM
and
python
by
using
pi
classes
and
Pi
methods.
Pi
classes
are
brush
structs
that
can
be
interpreted
as
python
objects
and
Pi
methods
are
Russ
methods
that
can
be
called
from
within
python.
So,
let's.
A
B
Well,
how
did
we
allow
it
to
modify
chiral
local
variables
and
carry
local
variables
can
be
accessed
inside
Hands
by
writing
ideas,
dot
the
name
of
the
variable,
so
what
we
did
was
override
these
IDs
objects,
set
attributes
and
get
attribute
methods.
So
when
we
want
to
get
an
attribute,
we
are
actually
calculating
the
value
of
that
attribute
inside
during
the
hinge
run,
and
we
want
to
modify
a
local
variable.
We
calculate
its
address
and
insert
the
new
value
into
memory.
Well,
the
next
step
was
execution
Scopes.
B
In
order
to
implement
this,
we
took
advantage
of
the
local
python
variables.
So
what
we
did
was
take
our
execution
scope,
variables,
convert
them
to
python
objects
and
inject
them
into
the
python
locals,
and
when
the
hint
was
done
running,
we
extracted
the
python
objects
from
the
locals
and
inserted
them
into
our
execution
Scopes.
This
is
how
executing
a
hint
currently
looks
like
we
first
take
this
to
our
local
variables
and
inject
them
into
python.
Locals
we
create
these
Pi
classes
that
will
allow
hints
to
interact.
B
And
insert
them
into
globals,
and
then
we
again
retrieve
these
values
from
python
locals
and
update
our
execution
scopes.
But
well,
how
does
this
all
look
like?
We,
we
created
a
separate
grade
for
this
called
Cairo
RS
Pi,
in
which
we
instantiate
the
VM,
and
we
execute
the
Cairo
methods,
debians
methods
such
as
initialization
running
instructions
and
when
a
hint
cannot
be
run
by
our
VM.
We
fall
back
to
this
python
hint
execution.
B
A
C
C
A
If
we
are
still
a
developing,
the
integration
with
python,
but
yes
Kairos
is
a
is
open
source
and
you
can
use
it,
but
we
are
finishing
I
think
in
maybe
two
weeks
and
they
implement
the
integration
with
python.
So
after
that,
we
are
going
to
start
a
testing
it
and
making
a
faster.
So
we
can
be
sure
that
everything
is
okay
and
then
where
it
comes
to
be
start
using
it
in
production.
So
we
are
really
excited.