{"action":"created","issue":{"url":"https://api.github.com/repos/ethereum/EIPs/issues/184","repository_url":"https://api.github.com/repos/ethereum/EIPs","labels_url":"https://api.github.com/repos/ethereum/EIPs/issues/184/labels{/name}","comments_url":"https://api.github.com/repos/ethereum/EIPs/issues/184/comments","events_url":"https://api.github.com/repos/ethereum/EIPs/issues/184/events","html_url":"https://github.com/ethereum/EIPs/issues/184","id":195163257,"number":184,"title":"Subroutines and Static Jumps for the EVM","user":{"login":"gcolvin","id":16827129,"avatar_url":"https://avatars.githubusercontent.com/u/16827129?v=3","gravatar_id":"","url":"https://api.github.com/users/gcolvin","html_url":"https://github.com/gcolvin","followers_url":"https://api.github.com/users/gcolvin/followers","following_url":"https://api.github.com/users/gcolvin/following{/other_user}","gists_url":"https://api.github.com/users/gcolvin/gists{/gist_id}","starred_url":"https://api.github.com/users/gcolvin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gcolvin/subscriptions","organizations_url":"https://api.github.com/users/gcolvin/orgs","repos_url":"https://api.github.com/users/gcolvin/repos","events_url":"https://api.github.com/users/gcolvin/events{/privacy}","received_events_url":"https://api.github.com/users/gcolvin/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":3,"created_at":"2016-12-13T05:12:27Z","updated_at":"2017-01-09T06:50:38Z","closed_at":null,"body":"```\r\npre-EIP: 184\r\nTitle: Subroutines and Static Jumps for the EVM\r\nStatus:\r\nType: Core\r\nAuthor: Greg Colvin, Paweł Bylica, Christian Reitwiessner \r\nCreated: 2016-12-10\r\nEdited: 2017-1-2\r\n```\r\n## Abstract\r\n\r\nThis EIP introduces new EVM opcodes and conditions on EVM code to support subroutines and static jumps, disallow dynamic jumps, and thereby make EVM code amenable to linear-time static analysis.  This will provide for better compilation, interpretation, transpilation, and formal analysis of EVM code.\r\n\r\n## MOTIVATION\r\n\r\nAll current implementations of the Ethereum Virtual Machine, including the just-in-time compilers, are much too slow. This proposal identifies a major reason for this and proposes changes to the EVM specification to address the problem.\r\n\r\nIn particular, it imposes restrictions on current EVM code and proposes new instructions to help provide for\r\n* better-optimized compilation to native code\r\n* faster interpretation\r\n* faster transpilation to eWASM\r\n* better compilation from other languages,\r\n   including eWASM and Solidity\r\n* better formal analysis tools\r\n\r\nThese goals are achieved by\r\n* disallowing dynamic jumps\r\n* introducing subroutines - jumps with return support\r\n* disallowing pathological control flow and uses of the stack\r\n\r\nWe also propose to validate - in linear time - that EVM contracts correctly use subroutines, avoid misuse of the stack, and meet other safety conditions _before_ placing them on the blockchain.  Validated code precludes most runtime exceptions and the need to test for them.  And well-behaved control flow and use of the stack makes life easier for interpreters, compilers, formal analysis, and other tools.\r\n\r\n## THE PROBLEM\r\n\r\nCurrently the EVM supports dynamic jumps, where the address to jump to is an argument on the stack. These dynamic jumps obscure the structure of the code and thus mostly inhibit control- and data-flow analysis.  This puts the quality and speed of optimized compilation fundamentally at odds.  Further, since every jump can potentially be to any jump destination in the code, the number of possible paths through the code goes up as the product of the number of jumps by the number of destinations, as does the time complexity of static analysis.  But absent dynamic jumps code can be statically analyzed in linear time.\r\n\r\nStatic analysis includes validation, and much of optimization, compilation, transpilation, and formal analysis; every part of the tool chain benefits when linear-time analysis is available.  In particular, faster control-flow analysis means faster compilation of EVM code to native code, and better data-flow analysis can help the compiler and the interpreter better track the size of the values on the stack and use native 64- and 32-bit operations when possible.  Also, conditions which are checked at validation time don’t have to be checked repeatedly at runtime.\r\n\r\nNote that analyses of a contract’s bytecode before execution - such as optimizations performed before interpretation, JIT compilation, and on-the-fly machine code generation - must be efficient and linear-time. Otherwise, specially crafted contracts can be used as attack vectors against clients that use static analysis of EVM code before the creation or execution of contracts.\r\n\r\n## PROPOSAL\r\n\r\nWe propose to deprecate two existing instructions - `JUMP` and `JUMPI`. They take their argument on the stack, which means that unless the value is constant they can jump to any `JUMPDEST`.  (In simple cases like `PUSH 0 JUMP` the value on the stack can be known to be constant, but in general it's difficult.)  We must nonetheless continue to support them in old code.\r\n\r\nHaving deprecated `JUMP` and `JUMPI`, we propose new instructions to support their legitimate uses.\r\n\r\n### Preliminaries\r\n\r\nThese forms\r\n* `INSTRUCTION x,`\r\n* `INSTRUCTION x, y`\r\n* `INSTRUCTION n, x1 ...`\r\n\r\nname instructions with one, two, and `n` arguments, respectively.  An instruction is represented in the bytecode as a single-byte opcode.  The arguments are laid out as immediate data bytes following the opcode.  The size and encoding of immediate data fields is open to change.  In particular, easily-parsed variable-length encodings might prove useful for bytecode offsets - which are in practice small but in principle can be large.\r\n\r\n### Primitives\r\n\r\nThe two most important uses of `JUMP` and `JUMPI` are static jumps and return jumps. Conditional and unconditional static jumps are the mainstay of control flow.  Return jumps are implemented as a dynamic jump to a return address pushed on the stack.  With the combination of a static jump and a dynamic return jump you can - and Solidity does - implement subroutines.  The problem is that static analysis cannot tell the one place the return jump is going, so it must analyze every possibility.\r\n\r\nStatic jumps are provided by\r\n* `JUMPTO jump_target`\r\n* `JUMPIF jump_target`\r\n\r\n   which are the same as `JUMP` and `JUMPI` except that they jump to an immediate `jump_target`, given as four immediate bytes, rather than an address on the stack.\r\n\r\nTo support subroutines, `BEGINSUB`, `JUMPSUB`, and `RETURNSUB` are provided.  Brief descriptions follow, and full semantics are given below.\r\n\r\n* `BEGINSUB n_args, n_results`\r\n\r\n   Marks the _single_ entry to a subroutine.  At least `n_args` items must be in the frame at entry to, and `n_results` items must be the frame at return from the subroutine. `n_args` and `n_results` are given as one immediate byte each.  The bytecode for a subroutine ends at the next `BEGINSUB` instruction (or `BEGINDATA`, below) or at the end of the bytecode.\r\n\r\n* `JUMPSUB jump_target`\r\n\r\n   Jumps to an immediate subroutine address, given as four immediate bytes.\r\n\r\n* `RETURNSUB`\r\n \r\n  Returns from the current subroutine to the instruction following the JUMPSUB that entered it.\r\n\r\nThese five simple instructions form the primitives of the proposal.\r\n\r\n### Data\r\n\r\nIn order to validate subroutines, EVM bytecode must be sequentially scanned matching jumps to their destinations.  Since creation code has to contain the runtime code as data, that code might not correctly validate in the creation context and also does not have to be validated prior to the execution of the creation code. Because of that, there needs to be a way to place data into the bytecode that will be skipped over and not validated.  Such data will prove useful for other purposes as well.\r\n\r\n* `BEGINDATA`\r\n\r\n   Specifies that all of the following bytes to the end of the bytecode are data, and not reachable code.\r\n\r\n### Indirect Jumps\r\n\r\nThe primitive operations provide for static jumps.  Dynamic jumps are also used for O(1) indirection: an address to jump to is selected to push on the stack and be jumped to.  So we also propose two more instructions to provide for constrained indirection.  We support these with vectors of `JUMPDEST` or `BEGINSUB` offsets stored inline, which can be selected with an index on the stack.  That constrains validation to a specified subset of all possible destinations.  The danger of quadratic blow up is avoided because it takes as much space to store the jump vectors as it does to code the worst case exploit. \r\n\r\nDynamic jumps to a `JUMPDEST` are used to implement O(1) jumptables, which are useful for dense switch statements, and are implemented as instructions similar to this one on most CPUs.\r\n* `JUMPV n, jumpdest ...`\r\n\r\n   Jumps to one of a vector of `n` `JUMPDEST` offsets via a zero-based index on the stack.  The vector is stored inline in the bytecode.  If the index is greater than or equal to `n - 1` the last (default) offset is used.  `n` is given as four immediate bytes, all `JUMPDEST` offsets as four immediate bytes each.\r\n\r\nDynamic jumps to a `BEGINSUB` are used to implement O(1) virtual functions and callbacks, which take just two pointer dereferences in C.\r\n* `JUMPSUBV n, beginsub ...`\r\n\r\n   Jumps to one of a vector of `n` `BEGINSUB` offsets via a zero-based index on the stack.  The vector is stored inline in the bytecode, MSB-first.  If the index is greater than or equal to `n - 1` the last (default) offset is used.  `n` is given as four immediate bytes, the `n` offsets as four immediate bytes each.\r\n\r\n`JUMPV` and `JUMPSUBV` are not strictly necessary.  They provide O(1) operations that can be replaced by O(n) or O(log n) EVM code using static jumps, but that code will be slower, larger and use more gas for things that can and should be fast, small, and cheap, and that are directly supported in WASM with br_table and call_indirect.\r\n\r\n## SEMANTICS\r\n\r\nJumps to and returns from subroutines are described here in terms of\r\n* the EVM data stack, usually just called “the stack”,\r\n* a return stack of `JUMPSUB` and `JUMPSUBV` offsets, and\r\n* a virtual stack of frame pointers (not needed at runtime).\r\n\r\nWe will adopt the following conventions to describe the machine state:\r\n* The _program counter_ `PC` is (as usual) the byte offset of the currently executing instruction.\r\n* The _stack pointer_ `SP` corresponds to the number of items on the stack - the _stack size_.  As an offset it addresses the current top of the stack of data values, where new items are pushed.\r\n* The virtual _frame pointer_ `FP` is set to `SP - n_args` at entry to the currently executing subroutine.\r\n* The _stack items_ between the frame pointer and the current stack pointer are called the _frame_.\r\n* The current number of items in the frame, `SP - FP`, is the _frame size_.\r\n\r\nPlacing the frame pointer at the beginning of the arguments rather than the end is unconventional, but better fits our stack semantics and simplifies the remainder of the proposal.\r\n\r\nNote that frame pointers and the frame pointer stack, being virtual, are only needed for the following descriptions of subroutine semantics, not for their actual implementation.  Also, the return stack is internal to the subroutine mechanism, and not directly accessible to the program.\r\n\r\nThe first instruction of an array of EVM bytecode begins execution of a _main_ routine with no arguments, `SP` and `FP` set to 0, and with one value on the return stack - `code size - 1`. (Executing the virtual byte of 0 after this offset causes an EVM to stop.  Thus executing a `RETURNSUB` with no prior `JUMPSUB` or `JUMBSUBV` - that is, in the _main_ routine - executes a `STOP`.)\r\n\r\nExecution of a subroutine begins with `JUMPSUB` or `JUMPSUBV`, which\r\n* push `PC` on the return stack,\r\n* push `FP` on the virtual frame stack,\r\n\r\n   thus suspending execution of the current subroutine, and\r\n\r\n* set `FP` to `SP - n_args`, and\r\n* set `PC` to the specified `BEGINSUB` address,\r\n\r\n   thus beginning execution of the new subroutine.   \r\n   (The _main_ routine is not addressable by `JUMPSUB` instructions.)\r\n\r\nExecution of a subroutine is suspended during and resumed after execution of nested subroutines, and ends upon encountering a `RETURNSUB`, which\r\n* sets `FP` to the top of the virtual frame stack and pops the stack, and\r\n* sets `PC` to top of the return stack and pops the stack\r\n* advances `PC` to the next instruction\r\n\r\n   thus resuming execution of the enclosing subroutine or _main_ program.\r\n   A `STOP or `RETURN` also ends the execution of a subroutine.\r\n\r\n## VALIDITY\r\n\r\nWe would like to consider EVM code valid if and only if no execution of the program can lead to an exceptional halting state.  But we must and will validate code in linear time.  So our validation does not consider the code’s data and computations, only its control flow and stack use.  This means we will reject programs with invalid code paths, even if those paths cannot be executed at runtime.  Most conditions can be validated, and will not need to be checked at runtime; the exceptions are sufficient gas and sufficient stack.  So some false negatives and runtime checks are the price we pay for linear time validation.\r\n\r\n_Execution_ is as defined in the Yellow Paper - a sequence of changes in the EVM state.  The conditions on valid code are preserved by state changes.  At runtime, if execution of an instruction would violate a condition the execution is in an exceptional halting state.  The yellow paper defines five such states.\r\n>**1**  Insufficient gas\r\n>**2**  More than 1024 stack items\r\n>**3**  Insufficient stack items\r\n>**4**  Invalid jump destination\r\n>**5**   Invalid instruction\r\n\r\nWe propose to expand and extend the Yellow Paper conditions to handle the new instructions we propose. \r\n\r\nTo handle the return stack we expand the conditions on stack size:\r\n>**2a**  The size of the data stack does not exceed 1024.\r\n>**2b**  The size of the return stack does not exceed 1024.\r\n\r\nGiven our more detailed description of the data stack we restate condition 3 - stack underflow - as\r\n>**3**  `SP` must be greater than or equal to `FP`\r\n\r\nSince the various `DUP` and `SWAP` operations are formalized as taking items off the stack and putting them back on, this prevents `DUP` and `SWAP` from accessing data below the frame pointer, since taking too many items off of the stack would mean that `SP` is less than `FP`.\r\n\r\nTo handle the new jump instructions and subroutine boundaries we expand the conditions on jumps and jump destinations.\r\n>**4a**   `JUMPTO`, `JUMPIF`, and `JUMPV` address only `JUMPDEST` instructions.\r\n>**4b**   `JUMPSUB` and `JUMPSUBV` address only `BEGINSUB` instructions.\r\n>**4c**   `JUMP` instructions do not address instructions outside of the subroutine they occur in.\r\n\r\nCondition **5** remains unchanged:\r\n>**5**   No instructions is invalid.\r\n\r\nWe have two new conditions on execution to ensure consistent use of the stack by subroutines:\r\n>**6**  For `JUMPSUB` and `JUMPSUBV` the frame size is at least the `n_args` of the `BEGINSUB`(s) to jump to.\r\n>**7**  For `RETURNSUB` the frame size is equal to the `n_results` of the enclosing `BEGINSUB`.\r\n\r\nFinally, we have one condition that prevents pathological uses of the stack:\r\n>**8**  For every instruction in the code the frame size is constant.\r\n\r\nIn practice, we must test at runtime for conditions **1** and **2** - sufficient gas and sufficient stack.  We don’t know how much gas there will be, we don’t know how deep a recursion may go, and analysis of stack depth even for non-recursive programs is non-trivial.\r\n\r\nAll of the remaining conditions we validate statically.\r\n\r\n## VALIDATION\r\n\r\nValidation comprises two tasks:\r\n* Checking that jump destinations are correct and instructions valid.\r\n* Checking that subroutines satisfy the conditions on control flow and stack use.\r\n\r\nWe sketch out these two validation functions in pseudo-C below.   To simplify the presentation only the five primitives are handled (`JUMPV` and `JUMPSUBV` would just add more complexity to loop over their vectors), we assume helper functions for extracting instruction arguments from immediate data and managing the stack pointer and program counter, and some optimizations are forgone.\r\n\r\n### Validating jumps\r\n\r\nValidating that jumps are to valid addresses takes two sequential passes over the bytecode - one to build sets of jump destinations and subroutine entry points, another to check that addresses jumped to are in the appropriate sets.\r\n```\r\n    bytecode[code_size]   // contains EVM bytecode to validate\r\n    is_sub[code_size]     // is there a BEGINSUB at PC?\r\n    is_dest[code_size]    // is there a JUMPDEST at PC?\r\n    sub_for_pc[code_size] // which BEGINSUB is PC in?\r\n    \r\n    bool validate_jumps(PC)\r\n    {\r\n        current_sub = PC\r\n\r\n        // build sets of BEGINSUBs and JUMPDESTs\r\n        for (PC = 0; instruction = bytecode[PC]; PC = advance_pc(PC))\r\n        {\r\n            if instruction is invalid\r\n                return false\r\n            if instruction is BEGINDATA\r\n                return true\r\n            if instruction is BEGINSUB\r\n                is_sub[PC] = true\r\n                current_sub = PC\r\n                sub_for_pc[PC] = current_sub\r\n            if instruction is JUMPDEST\r\n                is_dest[PC] = true\r\n            sub_for_pc[PC] = current_sub\r\n        }\r\n        \r\n        // check that targets are in subroutine\r\n        for (PC = 0; instruction = bytecode[PC]; PC = advance_pc(PC))\r\n        {\r\n            if instruction is BEGINDATA\r\n                break;\r\n            if instruction is BEGINSUB\r\n                current_sub = PC\r\n            if instruction is JUMPSUB\r\n                if is_sub[jump_target(PC)] is false\r\n                    return false\r\n            if instruction is JUMPTO or JUMPIF\r\n                if is_dest[jump_target(PC)] is false\r\n                    return false\r\n            if sub_for_pc[PC] is not current_sub\r\n                return false\r\n       }\r\n        return true\r\n    }\r\n```\r\nNote that code like this is already run by EVMs to check dynamic jumps, including building the jump destination set every time a contract is run, and doing a lookup in the jump destination set before every jump.\r\n\r\n### Validating subroutines\r\n\r\nThis function can be seen as a symbolic execution of a subroutine in the EVM code, where only the effect of the instructions on the state being validated is computed.  Thus the structure of this function is very similar to an EVM interpreter.  This function can also be seen as an acyclic traversal of the directed graph formed by taking instructions as vertexes and sequential and branching connections as edges, checking conditions along the way.  The traversal is accomplished via recursion, and cycles are broken by returning when a vertex which has already been visited is reached.  The time complexity of this traversal is O(n-vertices + n-edges)\r\n\r\nThe basic approach is to call `validate_subroutine(i, 0, 0)`, for _i_ equal to the first instruction in the EVM code through each `BEGINDATA` offset.  `validate_subroutine()` traverses instructions sequentially, recursing when `JUMP` and `JUMPI` instructions are encountered.  When a destination is reached that has been visited before it returns, thus breaking cycles.  It returns true if the subroutine is valid, false otherwise.\r\n\r\n```\r\n    bytecode[code_size]     // contains EVM bytecode to validate\r\n    frame_size[code_size ]  // is filled with -1\r\n\r\n    // we validate each subroutine individually, as if at top level\r\n    // * PC is the offset in the code to start validating at\r\n    // * return_pc is the top PC on return stack that RETURNSUB returns to\r\n    // * at top level FP = 0, so SP is both the frame size and the stack size\r\n    validate_subroutine(PC, return_pc, SP)\r\n    {\r\n        // traverse code sequentially, recurse for jumps\r\n        while true\r\n        {\r\n            instruction = bytecode[PC]\r\n\r\n            // if frame size set we have been here before\r\n            if frame_size[PC] >= 0\r\n            {\r\n                // check for constant frame size\r\n                if instruction is JUMPDEST\r\n                    if SP != frame_size[PC]\r\n                        return false\r\n\r\n                // return to break cycle\r\n                return true\r\n            }\r\n            frame_size[PC] = SP\r\n\r\n            // effect of instruction on stack\r\n            n_removed = removed_items(instructions)\r\n            n_added = added_items(instruction)\r\n\r\n            // check for stack underflow\r\n            if SP < n_removed\r\n                return false\r\n\r\n            // net effect of removing and adding stack items\r\n            SP -= n_removed\r\n            SP += n_added\r\n\r\n            // check for stack overflow\r\n            if SP > 1024\r\n                return false\r\n\r\n            if instruction is STOP, RETURN, or SUICIDE\r\n                return true\t   \r\n\r\n            // violates single entry\r\n            if instruction is BEGINSUB\r\n                 return false\r\n\r\n            // return to top or from recursion to JUMPSUB\r\n            if instruction is RETURNSUB\r\n                break;\r\n\r\n            if instruction is JUMPSUB\r\n            {\r\n                // check for enough arguments\r\n                sub_pc = jump_target(PC)\r\n                if SP < n_args(sub_pc)\r\n                    return false\r\n                return true\r\n            }\r\n\r\n            // reset PC to destination of jump\r\n            if instruction is JUMPTO\r\n            {\r\n                PC = jump_target(PC)\r\n                continue \r\n            }\r\n\r\n            // recurse to jump to code to validate \r\n            if instruction is JUMPIF\r\n            {\r\n                if not validate_subroutine(jump_target(PC), return_pc, SP)\r\n                    return false\r\n            }\r\n\r\n            // advance PC according to instruction\r\n            PC = advance_pc(PC)\r\n        }\r\n\r\n        // check for right number of results\r\n        if SP != n_results(return_pc)\r\n            return false\r\n        return true\r\n    }\r\n```\r\n\r\n### COSTS & CODES\r\n\r\nAll of these proposed instructions are O(1) with a small constant, requiring just enough work to unpack inline arguments, whereas a `JUMP` or `JUMPI` must do an O(log n) binary search of an array of `JUMPDEST` offsets before every jump. With the cost of `JUMPI` being _high_ and the cost of `JUMP` being _mid_, we suggest the following\r\n\r\n| Code | Operation | Cost     |\r\n| ---- |  --------- | ------- |\r\n| 0x4a | JUMPTO | low |\r\n| 0x4b | JUMPIF | mid |\r\n| 0x4c | JUMPV | mid |\r\n| 0X4d | JUMPSUB | mid |   \r\n| 0x4e | JUMPSUBV | mid |\r\n| 0x4f | RETURNSUB | mid  |\r\n| 0x5c | BEGINSUB | special |\r\n| 0x5d | BEGINDATA | special |\r\n\r\n\r\n### GETTING THERE FROM HERE\r\n\r\nThese changes would need to be implemented in phases at decent intervals:\r\n1. If this EIP is accepted, invalid code should be deprecated. Tools should stop generating invalid code, users should stop writing it, and clients should warn about loading it.\r\n2. A later hard fork would require clients to place only valid code on the block chain.  Note that despite the fork old EVM code will still need to be supported indefinitely.\r\n\r\nIf desired, the period of deprecation can be extended indefinitely by continuing to accept code not versioned as new - but without validation.  Since we must continue to run old code this is not technically difficult. \r\n\r\nImplementation of this proposal need not be difficult,  At the least, interpreters can simply be extended with the new opcodes and run unchanged otherwise.  The new opcodes require only a stack for the return offsets and the few pushes, pops, and assignments described above.  JIT code can use native calls.  Further optimizations include minimizing runtime checks for exceptions and taking advantage of validated code wherever possible."},"comment":{"url":"https://api.github.com/repos/ethereum/EIPs/issues/comments/271220389","html_url":"https://github.com/ethereum/EIPs/issues/184#issuecomment-271220389","issue_url":"https://api.github.com/repos/ethereum/EIPs/issues/184","id":271220389,"user":{"login":"VoR0220","id":7756785,"avatar_url":"https://avatars.githubusercontent.com/u/7756785?v=3","gravatar_id":"","url":"https://api.github.com/users/VoR0220","html_url":"https://github.com/VoR0220","followers_url":"https://api.github.com/users/VoR0220/followers","following_url":"https://api.github.com/users/VoR0220/following{/other_user}","gists_url":"https://api.github.com/users/VoR0220/gists{/gist_id}","starred_url":"https://api.github.com/users/VoR0220/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/VoR0220/subscriptions","organizations_url":"https://api.github.com/users/VoR0220/orgs","repos_url":"https://api.github.com/users/VoR0220/repos","events_url":"https://api.github.com/users/VoR0220/events{/privacy}","received_events_url":"https://api.github.com/users/VoR0220/received_events","type":"User","site_admin":false},"created_at":"2017-01-09T06:50:38Z","updated_at":"2017-01-09T06:50:38Z","body":"I need to digest this some more, but initial reading, I think that while it definitely makes the EVM more complex, it also has the potential to make it both more performant and potentially more safe since formal verification will likely benefit from this. "}}
{"actor":{"display_login":"VoR0220"}}