{"action":"created","issue":{"url":"https://api.github.com/repos/ethereum/cpp-ethereum/issues/3404","repository_url":"https://api.github.com/repos/ethereum/cpp-ethereum","labels_url":"https://api.github.com/repos/ethereum/cpp-ethereum/issues/3404/labels{/name}","comments_url":"https://api.github.com/repos/ethereum/cpp-ethereum/issues/3404/comments","events_url":"https://api.github.com/repos/ethereum/cpp-ethereum/issues/3404/events","html_url":"https://github.com/ethereum/cpp-ethereum/issues/3404","id":188156911,"number":3404,"title":"Static jumps & subroutines for O(n) analysis & optimization of EVM code","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":1,"created_at":"2016-11-09T02:51:58Z","updated_at":"2016-11-09T10:13:00Z","closed_at":null,"body":"This is a proposal to make minimal changes to the EVM to support static jumps and subroutines as an alternative to the existing dynamic jumps.  Absent dynamic jumps code can be analyzed in linear time, which opens up opportunities for validation and optimization of EVM code that are currently not workable, including the translation of stack code to register code, and the use of narrow registers for narrow data values.  This would make it unnecessary to add explicit 64-bit registers and operations to the EVM.\r\n\r\nTwo existing opcodes - `JUMP` and `JUMPI` - need to be deprecated.  They take their argument on the stack, which means they can jump dynamically to any valid destination.  As a result, traversing the control flow graph of an EVM program becomes quadratic (or worse?) rather than linear.  We will need to continue to support them, but at some point should stop allowing them in new code.  As replacements we will need\r\n> **JUMPTO** _dest_\r\n> **JUMPTOIF** _dest_\r\n\r\nThese are the same as `JUMP` and `JUMPI` except that they make a static call to an immediate _dest_.\r\n\r\nWe will also need a basic subroutine facility.  These opcodes delimit subroutines\r\n> **BEGINSUB**\r\n> **ENDSUB**\r\n\r\nThese opcodes make a static call to an immediate subroutine address, a dynamic call to an subroutine address on the stack, or return from a subroutine to its caller\r\n> **CALLSUB** _beginsub_\r\n> **CALLVSUB**\r\n> **RETURNSUB**\r\n\r\nCalls and returns are handled with an implicit stack of return values.  `CALLSUB` and `CALLVSUB` push the address of the instruction following the program counter on the return stack, then set the program counter to the called address.  `ENDSUB` and `RETURNSUB` reset the program counter to the value at the top of the return stack, then pop the return stack.\r\n\r\nTo be valid, EVM code must meet these conditions\r\n- Every `BEGINSUB` must be followed by an `ENDSUB`\r\n- Subroutines do not nest\r\n- A `RETURNSUB` can only occur within a subroutine.\r\n- Only the addresses of `BEGINSUB` codes can be called.\r\n- The depth of the stack at a `RETURNSUB` or `ENDSUB` must be the same as at the corresponding `BEGINSUB`.\r\n- Only the addresses of `JUMPDEST` codes can be jumped to.\r\n- The depth of the stack must be the same at all entries to a `JUMPDEST`.\r\n\r\nI believe that - and please correct me - all of these conditions and more can be statically determined, and can be determined in linear time in the absence of dynamic jumps.  Which means that code which fails such checks at create time can simply be refused admittance to the blockchain.  (Note that invalid code is still deterministic, so it is safe to skip validation for code that contains dynamic jumps.)\r\n\r\nAlthough all the optimizations that we do or plan for EVM code are linear time, they may still be too slow to run when a contract is called.  In that case the alternatives include to running the optimizations in parallel as a JIT, or running them when the contract is created and keeping the optimized code as private state.  I think the first might be more prone to attack, whereas the latter presents a speed/space tradeoff.\r\n\r\nFor convenient reference, the chart below includes all the existing opcodes, those already proposed for the EVM, and those I am proposing here.\r\n\r\nFor this proposal, the `POPN` code could make clearing the stack on subroutine return easier, and the `SWAPN` and `DUPN` proposed in https://github.com/ethereum/EIPs/issues/174 would let Solidity and other compilers generate code that is more easily optimized.\r\n```\r\n   Arithmetic     Logic & Bits   Algorithms     Env Info       Block Info     Locs & Amts    Push           Push\r\n   0              1              2              3              4              5              6              7\r\n   -------------  -------------  -------------  -------------  -------------  -------------  -------------  -------------\r\n0  STOP           LT             SHA3           ADDRESS        BLOCKHASH      POP            PUSH1          PUSH17\r\n1  ADD            GT                            BALANCE        COINBASE       MLOAD          PUSH2          PUSH18\r\n2  MUL            SLT                           ORIGIN         TIMESTAMP      MSTORE         PUSH3          PUSH19\r\n3  SUB            SGT                           CALLER         NUMBER         MSTORE8        PUSH4          PUSH20\r\n4  DIV            EQ                            CALLVALUE      DIFFICULTY     SLOAD          PUSH5          PUSH21\r\n5  SDIV           ISZERO                        CALLDATALOAD   GASLIMIT       SSTORE         PUSH6          PUSH22\r\n6  MOD            AND                           CALLDATASIZE                  JUMP           PUSH7          PUSH23\r\n7  SMOD           OR                            CALLDATACOPY                  JUMPI          PUSH8          PUSH24\r\n8  ADDMOD         XOR                           CODESIZE                      PC             PUSH9          PUSH25\r\n9  MULMOD         NOT                           CODECOPY                      MSIZE          PUSH10         PUSH26\r\na  EXP            BYTE                          GASPRICE                      GAS            PUSH11         PUSH27\r\nb  SIGNEXTEND     SHR                           EXTCODESZE                    JUMPDEST       PUSH12         PUSH28\r\nc                 SAR                           EXTCODECOPY                   JUMPTO         PUSH13         PUSH29\r\nd                 SHL                           CALLGAS                       JUMPTOIF       PUSH14         PUSH30\r\ne                 ROR                                                         JUMPTABLE      PUSH15         PUSH31\r\nf                 ROL                                                         POPN           PUSH16         PUSH32\r\n\r\n   Dup            Swap           Log                                                                        System Ops\r\n   8              9              a              b              c              d              e              f\r\n   -------------  -------------  -------------  -------------  -------------  -------------  -------------  -------------\r\n0  DUP1           SWAP1          LOG0                                                        SSTORE_COUNT   CREATE\r\n1  DUP2           SWAP2          LOG1                                                        SLOADBYTES     CALL\r\n2  DUP3           SWAP3          LOG2                                                        SSTOREBYTES    CALLCODE\r\n3  DUP4           SWAP4          LOG3                                                        SSIZE          RETURN\r\n4  DUP5           SWAP5          LOG4                                                                       DELEGATECALL\r\n5  DUP6           SWAP6                                                                                     REVERT\r\n6  DUP7           SWAP7                                                                                     STATIC_CALL\r\n7  DUP8           SWAP8                                                                                     SANDBOXED_CALL\r\n8  DUP9           SWAP9                                                                                     ASYNC_CALL\r\n9  DUP10          SWAP10\r\na  DUP11          SWAP11                                                                     BEGINSUB\r\nb  DUP12          SWAP11                                                                     ENDSUB\r\nc  DUP13          SWAP12                                                                     CALLSUB\r\nd  DUP14          SWAP13         DUPN                                                        CALLVSUB\r\ne  DUP15          SWAP14         SWAPN                                                       RETURNSUB\r\nf  DUP16          SWAP16                                                                     BAD            SUICIDE\r\n```"},"comment":{"url":"https://api.github.com/repos/ethereum/cpp-ethereum/issues/comments/259378627","html_url":"https://github.com/ethereum/cpp-ethereum/issues/3404#issuecomment-259378627","issue_url":"https://api.github.com/repos/ethereum/cpp-ethereum/issues/3404","id":259378627,"user":{"login":"pirapira","id":44281,"avatar_url":"https://avatars.githubusercontent.com/u/44281?v=3","gravatar_id":"","url":"https://api.github.com/users/pirapira","html_url":"https://github.com/pirapira","followers_url":"https://api.github.com/users/pirapira/followers","following_url":"https://api.github.com/users/pirapira/following{/other_user}","gists_url":"https://api.github.com/users/pirapira/gists{/gist_id}","starred_url":"https://api.github.com/users/pirapira/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pirapira/subscriptions","organizations_url":"https://api.github.com/users/pirapira/orgs","repos_url":"https://api.github.com/users/pirapira/repos","events_url":"https://api.github.com/users/pirapira/events{/privacy}","received_events_url":"https://api.github.com/users/pirapira/received_events","type":"User","site_admin":false},"created_at":"2016-11-09T10:13:00Z","updated_at":"2016-11-09T10:13:00Z","body":"`JUMPTOIF` still lets dynamic information leak into the control flow.  With this, the deprecated `JUMP` can be implemented.\r\n\r\nPoor man's `JUMP`:\r\n```\r\nDUP1\r\nISZERO\r\nJUMPTOIF 0x00\r\nDUP1\r\nPUSH2 0x0030\r\nEQ\r\nJUMPTOIF 0x0030\r\nDUP1\r\nPUSH2 0x0040\r\nEQ\r\nJUMPTOIF 0x0040\r\n... (for all jump destinations)\r\n```"}}
{"actor":{"display_login":"pirapira"}}