our next speaker will talk about Beyond
recours of approving for starnet please
welcome gon
CER hi
everyone let's see if you can hear
me okay so uh the goal of this
presentation is to talk about everything
Beyond recursive proving but I'm not
going to assume you know everything
about proving or recursive proving uh so
I'll just begin with the basics and uh
you'll uh follow me I
assume so uh let's talk about the basics
of a validity rollup what uh composes a
validity rollup you have
transactions uh sequencers select these
transactions Define their order and I'll
use the term sequencer also for
execution of these transactions so if
you're confused by base rollups where
they separate the sequencing from
execution here I'm going to combine them
um and they build the blocks uh once we
have a block uh the way a validity
rollup works is that it proves the
validity of the execution of these
blocks using a prover instance and send
this sends this proof per block to
verify our contract on ethereum on the
layer underlying layer one and once that
proof has been
accepted uh a state contract tracking
the state of the rollup is updated with
a new state uh together with the state
update we also uh add what we call State
diff and uh we may include also
messaging between the layer two and the
validity rollup and the underlying
Network State diff just to make sure you
understand what I mean when I talk about
State diff is basically the update to
the state of the rollup uh resulting
from the executed block uh validity
rollups do not need to transmit the
actual transaction that they sequenced
to the underlying layer there's no
context no uh uh such thing as fraud
proofs or anything of that kind we
positively prove everything happening on
a validity rollup and as a result we can
send much less much less data to the
underlying Network in order to be able
to reconstruct the full state of the
layer two so a state diff is basically
just the locations in the state that
have changed and their values so in this
simple example the has been changed into
X so the state diff of the transition
from State one to state two is just a
single element change location 3 to
Value
x what does it mean to prove a block so
basically what we're doing is we're
using the context of uh of uh proof in
order to
uh um to prove the statement that we
have seen a valid execution from a given
State a resulting in a new state B and
the resulting stative between State a
and state B is such and such so the
statement is the transactions were
correctly sequenced and the input State
results in the output
State what are we doing on layer one for
the validity rollup in this simple uh
basic validity rollup uh we need to
verify a proof of a block which can be
costly in some cases we need to publish
the state diff typically using blobs on
ethereum and we need to update the state
which is typically some contract call of
the state contract tracking the state of
the rooll up on L one um as long as the
blocks are significantly
large this is all this is fine but if we
want just to have a few transactions per
block on Layer Two or quick finality
this can become quite costly so the
basic validity rollup is good if you
have either a very large block
or you have a lot of traffic and then
you can still have a short finality on
Layer
Two or you have long finality then it
becomes less costly but it's less
effective because you have long
finality enter recursive
proving recursive proving intends to
reduce the overhead of verifying the
proofs per
block so let's begin with what recursive
proving really is so on the left hand
side you can see the generic uh concept
of proving so basically you have some
statement and you want to prove that
given a a current uh given an input or a
witness if you like uh there is a
correct execution of the statement
resulting in a given output and what the
prover does it basically proves that the
statement was run correctly on the input
and that the actual output is the given
output uh the proof does not necessarily
need to divulge the input as we call it
zero knowledge proofs but if you like to
include some of the input in the output
you can just copy that within the
statement so how do we use this context
uh this concept to create recursive
proving basically we replace the
statement with a new statement that just
says I verified two proofs and found
them to be correct uh so proof one with
output one and proof two with output two
you use a statement that performs
verification which is just an algorithm
right so there's no reason that you
can't uh build such a statement and the
result is the two outputs the original
outputs you just copy them from the
input to the output so when we prove
this statement exactly like on the left
hand side the result is a proof and the
outputs that we want to generate which
in this case are output one and output
two what does this mean we've basically
combined two proofs with two outputs
into one proof with two out
outputs now we can use this construct in
order to combine various statements
possibly totally different statements
from different sources if you like we
can prove uh statements from multiple
rollups even uh into a single proof and
a series of outputs uh coming from the
original inputs or from the original
statements I I should say so in this
diagram you can see four different
statements there's no relationship
between them each of them has their own
input creates the own their own output
and uh using recursive proving twice in
this example we result with one proof
and four
outputs so what does a validity rollup
with recursive proving look like very
very similar to what we had before so
you have the transactions the
sequencers Define the
sequence uh execute the transactions and
create blocks just like before in this
case let's say the accumulate four
blocks then we can use recursive proving
in order to prove these four blocks with
one proof as opposed to four proofs in
the previous example in the basic
validity roll up and this proof is sent
to the same verifier contract on layer
one then for every block a state update
takes place on layer one on the smart
contract that tracks the state of the
rollup and the statives per block are
sent to layer one so using recursive
proving we've basically reduced the cost
of verifying proofs on layer one but we
still keep uh the concept of publishing
State diffs per block and State updates
per transition so from State I to State
I + one that takes place per
block it's less costly than before
because sometimes a significant cost is
on the verification of the proof uh
State updates are less costly but
the smaller the blocks get the more
significant the cost of these State
updates become so this allows us to
improve uh to reduce uh block times on
Layer Two on the rollup or if you like
uh reduces the need to perform large B
batching on the blocks on layer to but
still I would like to optimize this
further which brings me to Beyond
recursive proving which is the topic of
my
discussion uh we want to build something
which we call applicative
recursion so let's define applicative
recursion roughly in the following way
here you see again the same recursive
proving tree that we had
before uh we have four input statements
uh we combine them together into a
single proof with four
outputs with applicative recursion uh
the difference uh from regular uh
recursive proving is that here we're
going to assume that all the statements
come from a single application so they
have some kind of common
semantics uh for instance these are four
proofs of blocks coming from the same
rollup then what we do is we use the
same context the concept of proving but
now for basically squashing the outputs
together into a single
output uh so in this case we'll have a
new statement which basically says this
is in the red rectangle on the bottom
basically we verify the last proof so we
make sure that the outputs are valid by
using verification of this proof and we
perform a statement that is a valid
combination of the four outputs into a
single output so the result is a single
proof with a single output this time so
let's see what this output could contain
okay so for example if we're interested
in aggregating state diff uh here is an
example of three state transitions so
we're moving from State one to state two
to state three and eventually to State
four in each transition we generate
State diff so in the first transition
you can see that position number three
has changed from D into X in the second
transition we're touching positions five
and six and in the last transition the
fourth transition from the third
transition from state three to State
four
uh we're changing position three again
and position six again so the result is
the
state called S4 on the bottom of the
slide but if you look at the resulting
stative between S1 and S4 there are only
three changes so there's no reason to
transmit three statives with six changes
as in this example so one of the things
that we can do in the squashing proof
this final step of applicative recursion
is joining the outputs together into a
single more concise output now in
reality for validity rollups it happens
quite a lot that the same positions in
the state are changed multiple times
even within a block and certainly
between blocks especially if there are
many many blocks or large blocks so this
kind of uh aggregation is very very is
very important to improve efficiency of
State div transmitted to the blockchain
but also other things can be done and
I'll go into examples in a moment so now
uh validity rollup looks like this you
have the transactions as you know
they're sequenced and
executed put into blocks for every set
of blocks we create a recursive proof
then we do the applicative recursion
because all these proofs relate to the
same application the same rollup in this
case so we can do that and this single
proof with the aggregated output a
single output is sent to the verifier on
layer one so we pay for verification
just like we paid for ver verification
in the previous example using simple
recursive proving but now instead of
doing a state update per block we can do
a state update per recursive cycle if
you like for multiple blocks together
simultaneously so what does uh this look
like so we have the recursive uh uh appc
applicative recursion
recursion per recursion we verify appr
proof and per recursion we publish the
aggregate State diff in one or more
blobs and update the state on the on the
contract that tracks the state of the
rollup with a single state update that
updates the state to the final State
we've reached after multiple blocks and
of course we can include messaging as
before so the more blocks we have Pro
recursion the lower layer one cost will
be and this basically skills infinitely
uh depending on the latency you require
uh to layer one
um and uh this is actually what we are
doing currently on our rollup uh called
Stark
net what else can be done in this uh
applicative squashing or if you like an
applicative
recursion so the basic uh aggregation of
State diffs as I mentioned is just uh a
straightforward aggregation but you can
also do more sophisticated things for
instance if you want to represent your
state in a more efficient way so utilize
your blobs more efficiently you can
Implement for instance a compression
algorithm on this data uh just deflating
the data into much smaller form which
allows you to uh include more blocks on
your applicative recursion of course
eventually when all the blobs fill up uh
you may reach a state where blob prices
could go up or you have more blobs than
could fit in a single transaction and
things like that that is something you
want to avoid so that's a point where
you want to cut off the applicative
recursion so it's not really infinite as
I mentioned before in addition as I
mentioned you can uh remove the need to
do update States per block and if you
like you can generalize this into a con
into a concept of segmenting a very
large computer ation into multiple
segments so if you prove that you've
executed a program from some State a to
some State B and then you've executed
the same program or continuation of the
program from State B to State C Etc an
applicative recursion or the squashing
mechanism can ensure that you've
actually proven the complete execution
of this program from State a all the way
through State C or Zed or whatever uh so
this is the generalization of the
concept of applicative recursion and you
may have more ideas here and uh the more
creative you get the more interesting it
gets so basically if you think about it
uh the whole concept of recursive
proving applicative proving is are a few
examples of offchain proving so these
are proofs that are never submitted to a
verifier on layer one so basically
they're only submitted to a new
statement that verifies them off chain
completely and there are other examples
that are useful in in this context and
I'll talk about a few of these so one
example could be for instance for a
privacy preserving uh uh exchange for
example so let's say you have an
exchange on your rollup on the
blockchain itself typically exchanges
that are on chain they expose the
positions of their
users uh some users are very sensitive
to this information because it divulges
a trading Str strategies so what you can
do is basically have a user who knows uh
their own
position uh execute uh some order on
their
position while keeping the position
encrypted on the on the rollup itself or
on the blockchain if you like so in this
example if I go over the diagram you
keep you store encrypted positions on
the blockchain every user uh is involved
in the encryption of this of this
position by using their own key they can
read the encrypted position decrypt it
and then execute an order on their own
position and encrypt the resulting or
the resulting position now if they prove
to a contract that
executes um trades that this would be
the result of their encrypted position
if for instance they get a little more e
selling a little bit of Bitcoin
uh then a trading contract or if you
like an exchange can accept that proof
without actually knowing the contents of
the current position so of course this
does divulge some information because uh
we are telling the exchange uh by how
much how much we are selling and how
much we are buying but anyone looking at
the position of a given uh user wouldn't
be able to decipher the current strategy
of this Trader so this is one example
where proofs can be combined into a
blockchain in order to create a more
private
environment uh by using client side
proving in this example there are
variants of this concept uh where we
trust the exchange with our private
information and then all the positions
can be encrypted and decrypted by the
exchange as part of uh proving uh but
this is one interesting example U that
can also be implemented on uh rollups or
blockchains as long as you have a
contract that can verify uh proofs uh on
Stark net we have contracts verifying
Stark proofs uh we also have a contract
verifying gross extin proofs so you have
a choice of building your application on
top of that and Stark net
today another example is for scaling
blockchains and this will be my final
slide so for everyone uh uh pressed for
time um this is a little bit more
sophisticated but the idea is let's say
I have a bottleneck in terms of the
capacity of sequencing and execution of
what's going on in the in the rollup I
want to Outsource sequencing to someone
else if you like or I want to Shard my
layer my uh validity rollup so that
different sequencers can run together in
parallel sequencing different parts of
the rollup or different contracts if you
like some segregation of
transactions so in this context you
basically what you see here is something
that looks like two rollups but they are
actually the same rollup so you have
multiple sequencers each executing part
of the sequencing for the rollup and
proving this sequencing is correct using
the validity concept where the output of
this proof is the state diff or the
changes to the state in the areas that
they're responsible for an underlying
sequencer that which is the validity
rollup sequencer can verify these proofs
completely remaining on the rollup
doesn't have these proofs don't need to
be sent to
ethereum and by verifying these proofs
uh this centralized or this rollup
sequencer can accept the state diffs
coming from these various shards or what
we call ZK threads and when we combine
the state of all the threads we result
in a single state of a single rollup
that can be as in the previous story
transmitted to ethereum with various
kinds of
proving uh resulting in a unified uh
rollup that has all the state computed
by multiple sequencers so here we
utilize uh validity
proofs uh in order to scale a
rollup that's it I think I have 3
seconds
left thank you we have now a few
questions could you
question so I think the first question
is how is aggregating State differ from
multiple blocks and is it better than
increasing the block time
itself um aggregating state is better
than multiple
blocks
uh no uh multiple blocks is better than
having a single aggregate block I'll put
it that way why because what use users
really want is finality on Layer Two on
the validity roll up itself so response
times go down the smaller the block is
uh of course if we would wait for an
hour to aggregate lots of transactions
in a block then we would had you we
would have huge blocks and the basic
validity roll up would work but finality
on Layer Two would be very
slow I also want to answer of about
about proving
cost um it's a good question because uh
in the past people thought uh that
proving I remember back in 2017 or
2018 uh the number thrown at people was
that proving a statement was something
like four orders of magnitude uh less uh
performant than actually executing that
statement at starkware I think our
initial prover reached about two orders
of magnitude H which is called the
stoneover and today we're talking about
a
Stover where execution of the statement
is almost the same as proving the
statement so the cost of proving has
gone down very very significantly well
it's not the same of course you still
have an overhead but to prove statements
today costs very very
little uh so all this recursive proving
for instance is done within seconds
every recursive step so you get a very
quick finality even of the recursive
proof and of course that doesn't cost
much okay um we have still time so um
what's the current transaction finality
on Stark net if you uh can yes currently
on starnet you get finality on Layer Two
within two seconds two seconds and this
two seconds will be preserved in a
decentralized environment where actually
block times will go down to 2 seconds
and we will continue to prove every
block so that's where we can go with
this
technology and maybe could this be used
for Crossroad lab Communications through
a shared approver absolutely uh in fact
in Stark net to in starkware I should
say today we already have a shared
prover it's called sharp sharp for
shared proving and we use it for many
systems together so we use it for public
Stark net we use it for private Stark X
instances we are layer 2 platforms for
exchanges we use it for app chains of
Stark net and all of the com all of
these proofs are combined into single
recursive proofs some of them are
applicative recursion some of them are
regular recursion and all of this is
submitted in a single proof attesting to
a huge number of execution steps across
multiple systems so of course this could
also be used for messaging between
different
rollups uh do we have any questions from
the audience no okay uh