Zoom in on EOF stack validation by Andrei Maiboroda | Devcon SEA

[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 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