[Music]
hello everyone who could wake up thank
you for
coming uh this talk is about EF uh we
had a very nice introduction thanks Alex
uh in the previous presentation so
hopefully you know by now this is a
series of
proposals that aims at redesigning and
improving evm in various ways and uh I
will be talking about one part of it one
EIP 5450 St
validation stack validation is in
general one part of a bigger code
validation procedure that happens before
code is being deployed on chain and one
of the leading principles and main goals
of it is uh to get rid of repeated
checks during executing the same code
and instead if we can if we can do the
check once before code is being deployed
then we do that and then assume it is
satisfied during uh execution and
then basically we can Adit the same
checks uh uh at runtime for stack
validation in particular this means
ensuring stack correctness of every
instruction in the code and in evm as we
don't have uh types of the values on
stack this simply means making sure that
none of the instructions overflow or
underflow the
stack and given that we check this once
uh at validation then we can omit these
checks from The Interpreter Loop and one
important consideration to keep in mind
when designing St validation is keeping
its complexity linear in the size of the
code uh this is important because we
cannot afford having some Rust case bite
codes exploding validation time and
enabling dos attacks with
that very high level overview of how St
validation would work we go through
control flow of the graph uh control
flow graph of the code uh examine every
instruction and see how many values it
pushes or Pops from the stack and keep
track of what is the current stack
height if it ever goes below zero we
detect detect underflow if it ever goes
above stack height limit we detect
overflow and reject this entire code AS
invalid and do not allow to for it to be
deployed uh this sounds pretty simple
and high level and you might wonder at
this point how is this even possible to
achieve without executing the code
because we are used to thinking about
underflows and overflows as depending on
the runtime uh value of the stack height
and uh depending on whatever runtime
conditions on call data or storage or
whatever I will show you that in fact
this is possible given that we impose
one extra restriction on what is allowed
in the code uh so let's zoom in and
explore how this would work
this was our initial approach to this
problem um and let's discuss underflows
first uh overflows are handled quite
differently I will mention this later so
every section is validated independently
one section at a time uh we Traverse the
control flow graph of the uh code in a
breadth resarch or depth res search
manner meaning we follow every jump uh
if it's a conditional jump we follow
both branches of the jump uh we keep
track of what is the current stack
height for every instruction and record
it
uh if it goes below zero we detect
underflow and reject this code AS
invalid and one extra restriction that
makes it all possible is the rule if we
ever uh encounter an instruction that
during out reversal that was already
visited before uh it means that this
instruction may be reached via multiple
possible code paths during execution and
uh in this case we require that the
stack height at this instruction is
equal for all possible code P leading to
it so this is something new comparing to
current evm so this makes some of the
patterns that were possible in current
evm uh invalid now in eof uh as a
practical
example for if then else statement you
would be required to have equal stack
height at the end of the than and else
branches for example or for Loops for
example the loop body is not allowed to
grow or Shrink stack these are pretty
reasonable restrictions to have other
vmss also have similar rules like jvm
and web
assembly and uh thanks to this rule we
just when we get to the branch that we
have already seen we just check this
condition and do not revalidate the same
Branch so in the end every branch is
validated exactly once every instruction
is visited exactly once so complexity is
linear for this algorithm which is what
we desired so this is great and one uh
extra rule that we have uh if after the
traval is finished some of the
instructions are not visited it means
they are never going to be reached in uh
execution and we do not allow this we do
not allow unreachable code to be
deployed and reject an entire bite code
AS
invalid I'll show an example now how
this would work here's a simple code uh
we'll need an array of Stack Heights for
every instruction and work list here is
a q like data structure that keeps track
of which branches we have yet to
validate so we start with first Branch
at offset zero uh push instruction would
add one value on the stack uh then call
data load doesn't change the St height
then this conditional jump instruction
has two possible successors at offsets
10 and five we add them both into the
work list and at this point we also have
to record the stack height uh at both of
the targets stack height is zero after R
jump I so we record that at both offsets
and continue then with the next Branch
from the work list we go to offset zero
there there's a push and another push
then a store checks whether it has
enough items not to under
underflow uh two is exactly enough for S
stor so no underlow happens we are good
here and we continue uh this stop then
validates uh uh concludes validation of
this branch and we have still one branch
left to examine at offset five we go
there there's another push and then
another jump into the Target that we
have already visited before at this
point we have to check whether current
stack height is equal to what we have
recorded for this target before it was
one previously and stack height is also
one for this after this R jump so 1
equals one and uh so this is valid we do
not revisit this Branch anymore and then
we do not have anything else in the work
list and this concludes the validation
this code is valid in the end compare
this to this invalid code it is very
similar but with one push emitted uh so
it goes through very similar steps and
ends up at this R jump
instruction uh and at this point stack
height is zero but we have seen stack
height one at the Target before and so
they are not equal and this means code
is invalid and
rejected so this uh exact restriction
that makes it all possible uh turned out
to be problematic in some important
cases so this code like on the slide uh
can be commonly generated by solidity
for example when you have a series of
requir statements in solidity every
require is a check and revert in case
it's not uh satisfied and then uh
solidity Optimizer at some point
extracts these reverts into a common uh
code uh common code block and uh then
each require becomes this check anded
jump into this common code uh so the
problem here these uh requires and these
checks and jumps can be located at
arbitary points in the function code and
at arbitary stack Heights and this goes
specifically against our rule that stack
height must be equal at
every every jump into uh common
code uh compilers could deal with it
with some workarounds for example they
could uh insert some extra Pop
instructions before some jumps to
equalize the stack and make it equal for
every jump into a common code but this
would mean increased code size and
increased gas consumed so this entire
optimization might not be worth it in
the end or another workaround could be
to take this revert and make an uh
separate code section out of it and call
it from here this would also work but
this also has an overhead of um putting
declaring this extra code section in the
UF header putting its metadata into type
section so in the end code size also is
increased and we might have some
regressions comparing to current evm
this is something we really would like
to avoid uh and this is just one common
examp example it's not the only one in
general compilers are very much um uh in
favor of being able to jump into some
common uh helper code blocks from
arbitrary stack
Heights so we found a solution to this
and this is current spec of 50450 and
final one uh so we have to modify our
algorithm somewhat in some important
ways uh uh we start with allowing
multiple possible stack Heights for
every instruction in instead of uh
recording just one stack height value we
record uh the range of Stack Heights to
minimum and maximum for every
instruction we change the way we
Traverse the code instead of uh depth
res search or bread for search reversal
we just do a sequential pass through
through the code uh front to back just a
simple Loop we do not follow jumps when
they see them instead we handle jumps
differently depending whether it's a
forward jump or backwards jump uh so
depending on its relative offset and
this is known at validation time because
EF has static jumps instead of dynamic
jumps so we look at this offset if it's
a forward jump we always allow it and we
just record the stack height at the
Target uh
instruction if we have already visited
this uh or we have already seen this
target instruction before we expand the
stack height range of the
Target and this specifically fixes our
problematic case
um we always allow this jumps into a
common code and thanks to sequential uh
traversal of The Code by the time we
reach the validation of this common
helper we have already seen all forward
jumps into it so we have seen already
all stack Heights uh at all of the jumps
into this common uh uh code and then we
validate it using this uh stack height
range that we have observed so this
fixes the problem and um as for backward
jumps uh we still keep the exactly same
restriction as before we require equal
stack height at the jump instruction and
at the target of a jump this means that
Loops that grow or Shrink stack are
still not allowed this is pretty
reasonable restriction to keep no
compilers generate such Loops anyway and
so they are fine with it uh if this
backwards jump is in fact a jump into a
helper not a loop uh it um this code
always can be reordered in a way that
jumps into a helper is a forward jump so
this is kind of an implicit require M to
put on the code ordering for compilers
to and this is always can be done and so
compilers are fine with
this if we see a regular instruction
which is not a jump we just modify both
ends of the stack height range both
minimum and
maximum uh stack underflow is checked
obviously using minimum end of the range
and one extra restriction on or one
change in how we Define unreachable code
this is very much related to backwards
jump rule that I have already mentioned
mentioned just now so we also uh expand
a bit the definition of what is UN
reachable code if some code is reachable
only via a backwards jump we also
consider it unreachable now this is
needed to make this sequential traversal
possible and this is all also always uh
achievable by compilers they need to do
some kind of topological sort ordering
of the basic blocks in the code uh and
uh it always can be done uh so this
restriction is fine some other uh VMS
also have similar
Rule and um also because we have this
simple Loop over all instructions every
instruction is visited exactly once so
we are still fine complexity wise
complexity is still
linear I'll show an example how this
would work now uh so we'll need an array
of two arrays of minimum and maximum
stack height or array of
pairs uh note that we do not need a work
list here because it's just a simple
Loop uh over instructions so we start
with the first one push uh is a simple
instruction that modifies both minimum
and maximum so 0 to0 becomes 0 1 to one
call data Lo doesn't change it then this
conditional jump uh it is a forward jump
so it is a load and we have just to
record the stack height at the Target it
is zero after or Pi so we record 0 to
zero at offset
X um uh then we continue with the next
instruction this is yeah another push
and push and C Lo and then another
conditional jump that targets the same
offset that we have already seen before
at this point uh stack height is one
after R jum pi and we have to at this
point expand the stack height range that
we have seen at the Target before so 0 0
becomes 01 then we have a stop with an
extra value on the stack this is allowed
and valid and then we get to this Branch
this is interesting Branch because it
has multiple possible St Heights it can
be either zero or one here then push
would modify both minimum and maximum so
it shifts the St height range 01 becomes
one two and another push and revert
checks for possible
underflow uh uh using minimum and two is
exactly what revert needs so no
underflow happens this code is valid in
the end this concludes the validation uh
note that this code is very similar to
the problematic case uh that I showed a
couple of slides before this is like a
common helper that reverts and a couple
of jumps from different stack Heights
into
it uh so given this algorithm uh
concludes successfully uh we are
guaranteed that no underflows happen at
run time uh ever at all uh and we can
completely Amit them from the
interpreted Loop this is not the case
with overflow checks uh we cannot remove
them uh completely but we can minimize
how often we do them and not do them for
every instruction as current evm
does uh so to make this uh work we start
with the with what previous underflows
uh validation algorithm gave us we
recorded stack height at every
instruction in this algorithm and we can
just find maximum of these stack Heights
and this value value is going to mean
maximum stack height value of this
functions frame if this value is above
stack height limit it means execution of
this function May overflow and we reject
it immediately at validation we do not
allow it to be deployed uh if it is
within the limit we record this maximum
stack height value in this functions
metadata the EF header and then this
value is used for validating the calls
into this section and also at execution
time when we execute call F for jump F
into this uh function so in the end we
only have to do runtime overflow checks
at two uh locations in the code for when
we execute call F or jump F we get the
current runtime stack height we add it
up with maximum stack height of the
call if this sum is above the stack
height limit we do not allow callif a
jump we exceptionally abort at call F or
jump F otherwise uh um execution could
overflow execution of this uh eof
function so this is how overflows are
handled and uh one final thing that I
wanted to mention is non- returning
functions and jump F these are defined
in their own EIP but they are closely
related to stack validation and
partially motivated by Stack validation
I would say so non functions are those
that do not return control back to a
caller they do not execute red f
instruction or you could think of them
as functions that and entire contract
execution with instructions like stop
return revert
Etc uh how is this relevant to stack
validation um so when we validate a call
to such a non-returning
function if there's some code
immediately following this call uh this
code is never going to be executed at
run time because this call is not
returning this means that we do not need
and we should not validate this code
following the call to non
returning instead we should uh consider
it unreachable and reject it as we do
with other unreachable code uh so to
make this work stack validation has to
detect calls to non- returning functions
somehow for that we have a special flag
in the EF header in the functions
metadata so when stack validation uh
detects a call when it sees a call it
checks this flag whether it's returning
or non rur if it's a call to non-
returning function it considers this
call to be a terminated instruction and
then uh in the end then if there's some
code immediately following it it it may
be unreachable unless there was some
previously seen forward jump into it so
this is how it works what's important
here is that calls to returning and non-
returning functions are validated very
differently so for calls to returning
functions you have to take into account
how many values were returned put them
on stack and continue validation and
calls to non- returning ad just
terminating instructions
given this difference I would say uh a
separate instruction for C return is
already Justified so this is exactly
what jump F instruction is if you need
to do a call to non function you uh use
jump f for that call F to non returning
is not allowed in
fact uh jump F also has different use
case it can be used with returning
functions but uh this does not fit this
presentation but you can read more
details in the EIP or some discussion at
this another
link and this is what all that I wanted
to say about this thank
you thanks a lot that was a very
interesting presentation so let's start
uh with uh the questions uh the most
popular one is um uh good stack
validation allowed translation to a
register based instruction set
internally reducing dispatch overhead in
The Interpreter
loop I think definitely it
can any any translation is easier uh in
eof given that we have we do not have
Dynamic jumps that's the main reason
that we can do jittin we can compile to
whatever backand uh it's yeah there are
various ideas about what EF can be
compiled to uh uh not
yeah interesting topic yeah okay the
next question is since stack size can
vary with recursion which is only known
uh at run time how can this method
ensure St stack Overflow is detected
statically good question so it is we
still uh uh require runtime for overflow
we just don't do them every time at
every
instruction so uh the recursive calls
will still do the Overflow check when
they do a call callif or jump off
instruction and in case uh this call May
overflow this call is not going to be
succeeded so overflow checks are not
checked completely statically that's
that's the
answer great uh so the next question I
think uh in the beginning you mentioned
that uh some compiler optimizations
won't be worth it so I guess uh which
compilers optimizations won't be worth
yeah so I refer to this one specific
case that uh was pretty common for our
uh initial idea of Stack validation uh
there uh the optimization that I meant
was uh the application that solidity
compiler does when it sees uh a similar
code at at multiple uh points in the
bite code it gets them and distracts
them into a common Helper but like with
the first algorithm there was some
overhead and in the end this might not
be worth it and because code size in the
end may increase and gas also
increased mhm uh so uh what does why
does this need needs to be part of eof
instead of just relying on the compiler
to H uh to handle stack access
efficiently
interesting
um well I would
say there is a value definitely some
value in ensuring St correctness of the
bite code
itself uh because it can it bite code
itself then can be audited or can be
formally verified or can be statically
analyzed so St validation and validation
in general uh uh simplifies these tasks
and uh uh immensely I would say so
that's the answer I think so if it
wouldn't be enforced on the protocol
level
then high level uh the same only the
high level Lang language code would be
available
to uh to use these benefits I think
Soh makes sense uh so the next one is uh
if the code passes uh stock range
validation um is it possible that there
is a code path that under overflows the
stock there is uh possibility of
overflows but not underflows that's the
answer yeah um underflows are completely
eliminated thanks to static validation
at at uh deployment time and overflows
still can happen but uh we do not need
to check them at every instruction as I
as I said mhm uh uh and um the next
question is uh if St validation makes uh
ZK cross compilation or ZK Trace
aromatization easier or
harder it definitely makes it easier if
in case this ZK compilation targets eof
only eof and does not try to support
Legacy 2 in case it is ZK system that
tries to support both Legacy execution
and UF execution then it has to
basically support two different systems
that is big pain I guess so it's
generally much better idea to support EF
for them and uh
then thanks to code validation and
thanks to uh deleting code observability
ZK compilation becomes much easier
that's at least the theory and yeah
we'll see how this works
out okay and uh I guess last question uh
will gas fee reduce after the
optimization and if so how much there
was no exact plans to reduce gas but uh
we definitely will see some uh
improvements in in in execution time and
this might lead to some optimizations in
the
future uh there will be gas savings
thanks to better stack management this
is like not uh specifically related to
validation but rather to a better just
better instruction instructions to
handle values on stack uh we have now
Swap and d and and exchange and all
these uh simplifies life for compilers
and in the end reduces gas consumed for
entire
execution great how much can I say uh
let's thanks um