Brainstorming OP_EVAL

#1

With the VM limits CHIP in place I think we could now implement OP_EVAL safely. Whatever it executes could count against the same budget as parent Script so OP_EVAL wouldn’t be able to cheat to amplify execution cost, and it couldn’t be used to turn the Script to be Turing-complete because it would inevitably hit the total limit by the VM limits CHIP.

Recall Gavin Andersen’s BIP-0012 definition:

OP_EVAL will re-define the existing OP_NOP1 opcode, and will function as follows:

  • When executed during transaction verification, pops the item from the top of the stack, deserializes it, and executes the resulting script.
  • If there is no item on the top of the stack or the item is not a valid script then transaction validation fails.
  • If there are any OP_CODESEPARATORs in the deserialized script then transaction validation fails.
  • If there are any OP_EVALs in the deserialized script they are also executed, but recursion is limited to a depth of 2.
  • Transaction verification must fail if interpreting OP_EVAL as a no-op would cause the verification to fail.

Example, the script 0x00027551b0 would result in value of 1 on stack and pass. How so? Decompiled, that is <0> <0x7551> OP_EVAL, and 0x7551 decompiles to OP_DROP OP_1 so execution would go:

  • push 0 on stack
  • push 0x7551 on stack
  • pop 0x7551 from stack
  • execute 0x7551 with starting stack state: {0}
  • execution ends with stack state: {1}

Later, Bitcoin Unlimited was proposing OP_EXEC (now active and in use on their Nexa network), which gave more thought about interaction with stack:

  • OP_EXEC executes a subscript that is presented as data in a script. This subscript is executed in an isolated stack environment – it can neither read nor modify elements on the main or alt stacks. Any illegal operation fails validation of the entire script ( T.o1 ).
  • A zero length stack element is a valid script (that does nothing) ( T.o2 ).
  • As with any scripts, any pops of an empty subscript stack fail, which fails the entire script ( T.o3 ).

Note that a space-efficient implementation does not need to recursively start another script machine instance with new stack objects. It can execute the subscript on the existing main and altstack, with the addition of a barrier to ensure that the subscript does not access (read, write, or pop) more than the provided N params.

I think we could implement this idea but in a simpler way. Have OP_EVAL “freeze” some N bottom stack elements, so it would be called as

<bytecode_to_execute> <N_freeze> OP_EVAL.

If we apply it to above example, then 0x0002755151b0 would fail while 0x0002755100b0 would pass, because decompiled it would be:

  • <0> <0x7551> <1> OP_EVAL and there the inner OP_DROP (0x75) would fail because it would try to access bottom stack item without permission, and
  • <0> <0x7551> <0> OP_EVAL would pass because it would have the permission and would succeed at dropping the 0 and replacing it with a 1.