Mode to Disable Jumps and Turing-Completeness

[igormcoelho]

Many applications (so many!) could benefit of a jump-free execution mode, where execution is bound to the number of opcodes, at most. Could we provide such a way now? It could be a flag passed to the execution engine, e.g. nojumps. This would also require disabling recursive calls and perhaps all calls.

[vncoelho]

Agree, brother, bye bye Turing.

This is a good possibility for those that wants their smart contracts to run within this context.

[shargon]

I can't see the benefits of this, you can avoid to use this opcodes

[vncoelho]

It can be an option that also blocks jumps after dynamic invoke for exmaple.
This would be a kind of scope limit for those that want to ensure this way of execution

[igormcoelho]

I can't see the benefits of this, you can avoid to use this opcodes

The point is: you could invoke a contract that has these opcodes in it, but your execution is guaranteed to not pass over them... the main idea is to disable loops in fact, but this should not affect ifs (and jumps are needed here). Perhaps a better idea is to limit jumps to forward positions only, I need to think...

If we have this mode enabled on vm, we could update compilers to use a flag --no-loops, in order to manually unroll loops for us (or using a decorator). Nearly all existing contracts would work better with a guaranteed maximum number of steps on loops, but if vm allows them, we can never be sure that code will finish in a given time.
Another application is to use them inside OP_EVAL, so we know that infinite loops won't ever exist inside user operations.

[igormcoelho]

Guys, I think only Turing-incomplete opcodes should be used on a very fast verification:

        PUSH0 = 0x00,  
        PUSHF = PUSH0,
        PUSHBYTES1 = 0x01,
        PUSHBYTES2 = 0x02,
        ...
        PUSHBYTES75 = 0x4B,
        PUSHDATA1 = 0x4C,
        PUSHDATA2 = 0x4D,
x      PUSHDATA4 = 0x4E, <-------------- This should be disabled on Neo 3.0. Too much memory!
        PUSHM1 = 0x4F,
        PUSH1 = 0x51,
        PUSHT = PUSH1,
        ...
        PUSH16 = 0x60,
        NOP = 0x61,
        /// <summary>
        /// Reads a 2-byte value n and a jump is performed to relative position n-3.
        /// </summary>
x        JMP = 0x62, <------ JUMP should only be allowed to a positive value (during verification)
        /// <summary>
        /// A boolean value b is taken from main stack and reads a 2-byte value n, if b is True then a jump is performed to relative position n-3.
        /// </summary>
x       JMPIF = 0x63, <------ JUMP should only be allowed to a positive value (during verification)
        /// <summary>
        /// A boolean value b is taken from main stack and reads a 2-byte value n, if b is False then a jump is performed to relative position n-3.
        /// </summary>
x       JMPIFNOT = 0x64, <------ JUMP should only be allowed to a positive value (during verification)
        /// <summary>
        /// Current context is copied to the invocation stack. Reads a 2-byte value n and a jump is performed to relative position n-3.
        /// </summary>
x        CALL = 0x65, <------ CALL should only be allowed to a positive value (during verification), no recursive behavior
        RET = 0x66,
x        SYSCALL = 0x68, <-------- SYSCALL should be controlled on Application layer. No implicit loops should be done, or expensive blockchain searches (GetTransaction, GetBlock, ...). Storage read is fine.

        DUPFROMALTSTACKBOTTOM = 0x69,
        DUPFROMALTSTACK = 0x6A,
        TOALTSTACK = 0x6B,
        FROMALTSTACK = 0x6C,
        XDROP = 0x6D,
        XSWAP = 0x72,
        XTUCK = 0x73,
        DEPTH = 0x74,
        DROP = 0x75,
        DUP = 0x76,
        NIP = 0x77,
        OVER = 0x78,
        PICK = 0x79,
        ROLL = 0x7A,
        ROT = 0x7B,
        SWAP = 0x7C,
        TUCK = 0x7D,


?        CAT = 0x7E,  <-------- CAT should be controlled. CAT + CAT + CAT + CAT.. is not good, too much memory. Since we have a limit for this, no problem.
        SUBSTR = 0x7F,
        LEFT = 0x80,
        RIGHT = 0x81,
        SIZE = 0x82,

        INVERT = 0x83,
        AND = 0x84,
        OR = 0x85,
        XOR = 0x86,
        EQUAL = 0x87,


        INC = 0x8B,
        DEC = 0x8C,
        SIGN = 0x8D,
        NEGATE = 0x8F,
        ABS = 0x90,
        NOT = 0x91,
        NZ = 0x92,
        ADD = 0x93,
        SUB = 0x94,
        MUL = 0x95,
        DIV = 0x96,
        MOD = 0x97,
        SHL = 0x98,
        SHR = 0x99,
        BOOLAND = 0x9A,
        BOOLOR = 0x9B,
        NUMEQUAL = 0x9C,
        NUMNOTEQUAL = 0x9E,
        LT = 0x9F,
        GT = 0xA0,
        LTE = 0xA1,
        GTE = 0xA2,
        MIN = 0xA3,
        MAX = 0xA4,
        WITHIN = 0xA5,


x        SHA1 = 0xA7, <------ these are expensive, should be controlled by price or count
x       SHA256 = 0xA8, <------ these are expensive, should be controlled by price or count

        ARRAYSIZE = 0xC0,
        PACK = 0xC1,
        UNPACK = 0xC2,
        PICKITEM = 0xC3,
        SETITEM = 0xC4,
        NEWARRAY = 0xC5,
        NEWSTRUCT = 0xC6,
        NEWMAP = 0xC7,
        APPEND = 0xC8,
        REVERSE = 0xC9,
        REMOVE = 0xCA,
        HASKEY = 0xCB,
        KEYS = 0xCC,
        VALUES = 0xCD,

        THROW = 0xF0,
THROWIFNOT = 0xF1

[igormcoelho]

@erikzhang @shargon @lightszero what about only allowing these opcodes during Neo 3.0 verification?
All the proposed checks here could run before actually executing any code. Price (network fee) could be charged regardless of any jumps.
Perhaps deployed contracts could have two codes: one for Trigger Verification and another for Trigger Application.
Example: Contract.Create ... opcodes_verif opcodes_appl. So, verification opcodes could be attached to the transaction, and be fully prepared for turing incompleteness. Otherwise, contracts (compilers) should make sure that no invalid operations occur during verification branch (this is easy to test).

[shargon]

Could you give me a practical example of why this is needed

[igormcoelho]

This allows us to calculate a tight upper bound of contract cost, regardless of its parameters. I give you the opcodes and I know the cost without executing them (reading storage, taking branches...). This is perfect for verification, and thats wht bitcoin still uses it.

[erikzhang]

How to check signature without SYSCALL?

[igormcoelho]

SYSCALL will be controlled on Application layer Erik.
I can provide another list here with my opinion on it. Based on interop prefix, we could remove most operations (ledger dependent) during verification, and only O(1) ops. Example VERIFY. Anyway, we could put a price on it, but considered as network fee, not system fee (because it takes time from p2p nodes).

[igormcoelho]

Here's the proposed list of what should be allowed on verification Syscalls:

https://github.com/neo-project/neo/blob/master/neo/SmartContract/InteropService.cs

========= INTEROP NAME ==========       REASON 
ok System.ExecutionEngine.* : simple environment get variables
ok System.Runtime.* : important information of runtime (triggers, platfrom, ..)
ok System.Crypto.* : cryptography (ecc validation, etc). Costly, but necessary (gas price network fee would compensate this)
x  System.Blockchain.*: access to blockchain should be forbidden, since it could be costly.
ok System.Blockchain.GetHeight: the only exception is height, that it's cheap and could be acessible
? System.Blockchain.GetContract: perhaps it should be allowed to getcontract here, to access info? IsPayable? Not very useful without the ability to call it.
x System.Header.*: processing batches of transactions is possibly costly (no header available due to no access to the chain)
x System.Block.*: no access to block info either
x System.Transaction.* : no way to instantiate a transaction and get info
? System.Contract.Call: perhaps allow to call a single contract, manually on Transaction field. after that no more invocations.
x System.Contract.Destroy: no destroy on verification
ok System.Storage.Get* : allow gets on storage, but no Puts and no Deletes
ok System.Storage.AsReadOnly: no harm in doing this (just a casting, right?)

https://github.com/neo-project/neo/blob/master/neo/SmartContract/InteropService.NEO.cs

x Neo.Native.Deploy: no deploy on verification
ok Neo.Crypto.*: allow all crypto checks, including checkmultisig. The reason is that, although multisig includes an implicit loop, this loop is limited to the number of operands in the transaction, so it is already limited to tx size (no infinite loops) and user must pay for tx size already. Every ecc verification should have a cost anyway, so it's the same as a batch of ecc checksig.
x Neo.Header.*: no header
x Neo.Transaction.*: no transaction
ok Neo.Account.IsStandard: no harm on this
x Neo.Contract.*: no contract access (create, delete,)
ok Neo.Contract.IsPayable: this may be useful. however, must find a way to get contract first
x Neo.Storage.Find: I don't think FIND should be allowed... it has an implicit loop which is not good, even paid.
? Neo.Enumerator.*: don't know about these
? Neo.Iterator.*: don't know about these. It has implicit loops and concats, looking not good for fast verifications.

[shargon]

Related to neo-project/neo#790

[igormcoelho]

Just to clarify the proposed direction for Verification:

1. allow cryptography to happen, and charge it also as network fee (because all nodes will need to process it, including consensus nodes)
2. allow access to runtime information, trigger, etc.
3. disallow all sorts of access to past blockchain events. This is very important in my opinion, because the bigger the chain, the bigger will be the affected TPS.. we need to keep it flowing fast.

My questions here are:

1. disallow all write access, but allow storage reads.
   I think this gives network flexibility during verification. On the other hand, this makes nodes to have a (somewhat) complete state before performing verification. Any thoughts on this?
2. allow a single contract call
   I suggest to disallow all Call operations, except by the first one. This is useful to invoke a contract script, not passing it directly on verification, but not allowing it to dig deeper on other contracts. Any thoughts on this?
3. I don't like iterators very much on verification, because a storage may hide a bigger loop that is not visible on script. However, by cutting these, perhaps it's better to cut storage get entirely, as they usually work together, right? Back to (1), will we need storage get on verification?

[shargon]

But all is about gas, what do you think... the fee should be the verification and the execution fee?

[igormcoelho]

I think that, if we want to prevent consuming tx to enter mempool, this should be charged as network fee, instead of system fee. I mean, the VerificationScript (+InvocationScript) part yields network fees, and the Script itself (old InvocationTx.Script) part (that only runs after block is ready), yields system fees. If system fee is not enough, tx will FAULT. If no network fee is enough, tx won't even enter mempool. This is the way I see it.

Just to be precise here @shargon:
(1) the Witness part needs to be processed on real-time, so it would require network fee (tx size + expensive operands).
https://github.com/neo-project/neo/blob/master/neo/Network/P2P/Payloads/Transaction.cs#L36
https://github.com/neo-project/neo/blob/1044a817d29b860fdec7d9862af97570d1716cdd/neo/Network/P2P/Payloads/Witness.cs#L11-L12
(2) the Script part runs after block is relayed, and it requires system fees to not FAULT.
https://github.com/neo-project/neo/blob/master/neo/Network/P2P/Payloads/Transaction.cs#L30

[erikzhang]

If no network fee is enough, tx won't even enter mempool. This is the way I see it.

If we follow this way, we don't need to limit the opcodes. Why limit it?

[igormcoelho]

If we follow this way, we don't need to limit the opcodes. Why limit it?

The greatest advantage is to able to verify network fee without executing the code.

(Gas) Price is a way to prevent attacks to the network, correct? Bitcoin does not have gas, because it has (intentionally) a Turing-incomplete network. It's verification-based network, without storage, paying by tx size, so it's perfect for them. Since Neo and Ethereum have in common the fact to provide a Turing-complete network, and both require the concept of gas, to prevent things such as while(true) that cannot exist on Bitcoin.
The point is, we want to simplify Verification to make it faster and get more TPS, right? By adopting a Turing-incomplete design, plus the fact that larger tx already pay fees, we actually solve the problem.
But you raised another important issue, that some operations are costly (for example, ecc verification, sha, etc). So, the best way I see is to adopt a hybrid Turing-incomplete + charging only expensive operations on network fee.
This resolves everything in a beatiful design for Verification that fees strugle to represent. What's the cost of a JUMP? or an ADD? currently, it's the same as a NOP I think, the minimum fee of 1 gas satoshi. However, this is not good to prevent a while(true), because this would cost millions of useless operations, hurting TPS. So, what we can do? We raise the price of JUMP?
If we adopt a Turing-incomplete network on verification, this problem is solved, and simple operations can cost zero (not even one satoshi). We can charge more (much more) for expensive operations, and that's it. No future problems, no pricing problems. TPS will always be high.
For application trigger, it's another story, because some people would be willing to do any kind of weird stuff... and that's fine, as long as they pay for them. If they run out of credits, invocation will FAULT. If they somehow explore cheap operators in the future, they won't hurt TPS, only delay a little bit the network State, that I now fully agree with you, that must be dettached from block proposal.
I think things glue well this way Erik, that's why I'm insisting on it. This is better than leaving an infinite amount of possibilities on Verification, that may hurt TPS, or to fully abolish verification (by allowing only a ecc validation and that's it).

[igormcoelho]

Could you give me a practical example of why this is needed

@shargon you asked for a practical example, this is one:
00c56b620000

Your node receives this script for Verification. How much does it cost? You don't know before executing it. You cannot provide an upper bound on the cost. Someone attached 1 GAS, is it enough? We never know. So you execute it, and only stops it if it runs out of gas (and that takes time). (if one jump costs 1 satoshi, you will spend 10^8 useless operations here, until you fail by gas, and don't win anything since it's on verification).

Suppose the same thing on a Turing-incomplete network. How much will it cost?
I tell you, opcodes are:

00 0: PUSH0  
c5 1: NEWARRAY 
6b 2: TOALTSTACK 
62 3: JMP 0000

I don't execute it, but maximum cost of this is 4 opcodes (1 satoshi each? so it's maximum 4 satoshi). How do I know it? Because it's impossible to have loops here.

[shargon]

this example will be controlled by fee. You need to execute your verification for know the amount of required gas

[shargon]

My proposal:

Execute verification with the fee atached, the rest of the fee will be the fee for the invocation.

if your verification cost 10Gas,and your invocation cost 1 of gas, you need to attach 11 of gas, or your TX will fault by gas

neo-project/neo#791

[igormcoelho]

You need to execute your verification for know the amount of required gas

This is what I'm trying to avoid..... to know the gas without executing anything. In order words, for a O(K) length script, validate network fee in O(K).

Execute verification with the fee atached, the rest of the fee will be the fee for the invocation.

You mean, the unused part of the network fee to be converted into system fee automatically? This is hard because we don't know which priority the user wanted for the network... and to calculate the claim bonus it's useful to have separated system fee declared on the transaction. We still have that, right? (just checked, we still have two fields, Gas and NetworkFee): https://github.com/neo-project/neo/blob/2401a113cb51e52e4a3eb1136ad868fb07993e0e/neo/Network/P2P/Payloads/Transaction.cs#L32-L33

[erikzhang]

How do you calculate the count of opcodes? We can't get the count from script size. You'll have to do some static analysis.

But I think most of the verification can be done in the time of static analysis. So this may be a bit more than a move.

[shargon]

I agree with erik, parse and execution will spend more time than execution

[igormcoelho]

Parsing is linear on the tx size, meaning that it is ultra fast. No parsing is slower than a single ecc check, even for a thousand bytes.

[igormcoelho]

We should do it on ApplicationEngine.

[vncoelho]

This issue needs to be transfered to neo-project/neo#837, right, @igormcoelho?

[vncoelho]

Perhaps this is dealt on neo-project/neo#789, yes?

[shargon]

At the end, it was needed :)