foreign
[Music]
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 so if you if you have any
problem just give us a call
and okay let's go straight to to the
talk
and the first thing I want to start with
is to give a little bit of context and
talk a little bit about ethereum and as
you all may know ethereum is a
decentralized network meaning that when
you run it on suction the transaction is
not run in only one computer but in
every computer that forms part of
ethereum of the network
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
and here is where starnet comes into
play
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 so then on chain uh 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
so ah 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
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 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
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 so okay how does
the Caribbean works and now Federica
will guide us through the internals of
the Caribbean so ferrica soldiers well
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
so let's go a bit into the architecture
of the career virtual machine well first
we have the memory model it is the right
one's read-only memory that is divided
into different segments these segments
have a known size at runtime and once we
finish the BM run we these segments go
for a relocation process and we end up
with a continuous memory so well the
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 what when you say with base
is that is the first address of each
segment in the relocated memory so for
example for segment one we have the
previous segment base is one because
this is the first segment and we add
five which is the size and we get six
now with this space is calculated we'll
proceed to relocate all the addresses
we'll do this by adding the base of the
segment with the offset of the address
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
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
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 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 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
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 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 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
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
for example this code is a bit long but
we could just focus on for example we
first enter the scope with an N variable
then we use that n variable we modify it
for by situations 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 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 we had that it was very easy
to implement as we didn't need any new
tools and it also offered better
performance as calling functions within
the BM was much faster than compiling
and running code during the vm's run but
on the con side is that we needed to
watch out for changes 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 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 take a look at the code and
well this is how we allowed hints to
modify memory we created this Pi memory
object and when we want to get an item
what actually happens is that we call
our VMS memory and we use our rust get
function and the same happens when we
want to set an item
uh 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 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 with our VM
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
so with this approach we were able to
maintain the rest functions that we
created in the first iteration and also
add this python integration so when you
use the common Library hints you can
still enjoy the boosting performance
from the plus native functions okay
awesome thanks okay
um
well in the name of our talk is how we
improve the performance of private
computation so showing some Benchmark
with some must and here we can see how
our implementation of Cairo Cairo RS is
um about uh 100 100 times faster than
the Caribbean using the C python
interpreter and about 20 times faster
than the Caribbean using the Pi Pi
interpreter and the coolest thing is
that
the our implementation is 100 times
faster than a car VM using CC python but
also consumes half of the memory and our
implementation is 20 times faster than
the Pi Pi version but consumes 12th time
less memory than Pi Pi so yeah it's
really cool and yeah okay I hope that
standard development developers Embrace
a Kairos and that helps building and
accelerating the ecosystem so yeah
that's it thanks for being here
questions we still have time for some
questions so we have our Volunteers in
the room
just raise your hand if you have any
questions compliments for the great
presentation
um hello
hello
um well I've seen you before
um my question is how stable is this is
this available to use right now uh or
if it's available if tuition right now
yeah yes 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
we let them speechless about the
representation well maybe big round of
applause thank you so much for the
weekend Herman