Substitute call stack limit with child gas restriction

[vbuterin]

For blocks where block.number >= METROPOLIS_HARDFORK_BLKNUM, make the following changes:

1. The 1024 call stack limit no longer exists
2. Still keep track of the call stack depth; however, if the call stack depth is at least 1024 (ie. in and only in those execution environments which would never be reachable in the current Ethereum implementation because they would trigger the max call stack depth exception), a CALL, CALLCODE, CREATE or DELEGATECALL can allocate a maximum of (g * 63) // 64 gas to the child, where g is the remaining gas in the message at the time the call is made, after subtracting gas costs for the call and for memory expansion.

Option B: allow any amount of gas to be required, and if the amount of gas required is too high then don't throw an exception, instead just limit it to the maximum. Option B1: the maximum is 100% for call depths up to 1024 and 63/64 as above after, option B2: the maximum is 63/64 as above at all depths. If the limit is equal to the maximum, then if the call throws, immediately set the parent gas to 0 (this preserves a nice safety property that currently exists in contracts by default).

Assuming a block gas limit of 10**9 (a safe upper limit for the foreseeable future), and a minimum gas cost of ~50 for a call + pushing stack arguments + doing the arithmetic of * 63 / 64, we can compute a maximum de-facto stack depth of 1024 + log(10**9 / 50) / log(64 / 63) = 2091, so the stack depth remains very safely bounded. However, with this mechanism for enforcing a maximum call stack depth, contracts no longer have to worry about the remaining call stack depth in the execution environment they are running in, and possible attacks or bugs if the depth is too low, and instead only need to worry about the single limiting variable of gas.

[chriseth]

In general, I much prefer methods that use gas to limit resources (because that is what gas was designed for). The question here is how to retain backwards compatibility and make this practical at the same time. Currently, calls try to forward all gas in calls. In order to achieve this, some gas has to be retained to pay for the call opcode itself. So the gas that is sent via the call is gas - cost_of_call. The problem we already have is that it is extremely difficult to calculate the cost of the call opcode because there are a lot of factors that play into this:

• whether or not the target account exists
• whether or not we send ether along with the call
• how much we have to resize memory for input and output parameters

Not to forget that we have to take into account the costs for performing these calculations themselves.

If we even complicate this by restricting the amount of gas we can send along depending on the current call depth (a value that is impossible to retrieve inside the contract), it will even get worse.

Because of that, I would like to bring forward the following proposal:

• limit the amount of gas for a child call depending on the depth as explained in this issue
• if we want to send more gas than is available or allowed, the call does not fail but it just sends the max possible amount of gas

This has already been brought up in #90

Still, these are quite drastic changes that might break existing contracts. I do not think that contracts rely on that, but there might be other problems I did not see.

[vbuterin]

if we want to send more gas than is available or allowed, the call does not fail but it just sends the max possible amount of gas

I'd support this. Actually, combining this with @chfast 's idea from #90 seems like a very good idea, this way we resolve both issues at the same time.

Actually, if we are doing this, I'd strongly consider removing the exemption for the first 1024 units of call stack depth.

[chriseth]

Sure, the change does not affect the prior 1023 call depths, but we know that there are contracts that deliberately probe the stack call depth. Those will report "all is fine, go on" now, which is probably fine, because we can go on, only until such contracts also make assumptions about how much gas is still left for the recursive call. Which is probably also fine, but just saying :-)

So this change will modify the behaviour of existing contracts, but probably in line with their intent.

[gcolvin]

Having seen how expensive a small deviation of behaviour from apparent intent can be, 'probably' is not reassuring.

[gcolvin]

I also suspect that tracking gas use is actually more difficult for a programmer than a hard limit. From what I can tell programmers don't track it. They try to write correct code, then use tools to estimate gas usage, then throw in some extra gas to be sure. But they can count to 1024.

[gcolvin]

In general, I would prefer that the EVM have hard edges on its resource constraints. That makes it possible for the EVM implementation to optimize for the limits, (e.g. preallocate memory, use small indexes instead of big pointers, etc.) the systems running EVMs to provision for those limits, and programmers of the EVM to respect those limits. If it's all based on gas the limits become fuzzy, as they are now for memory. As computers become more powerful the limits can be increased.

[nicksavers]

... this change will modify the behaviour of existing contracts ...

Not if these changes would only apply for contracts which were created after the rule was implemented. Unfortunately there is no easy way to find out in which block a contract was added to the state. Adding a creationBlock to the account state or another way to easily figure that out, could have made backwards compatibility with EVM updates a lot easier.

[eth1au]

...optimal amount of gas

source: econresdata http://www.federalreserve.gov/econresdata/feds/2015/files/2015031pap.pdf

[vbuterin]

I think in this case using gas is fine because the call depth will go up only logarithmically with increasing gas counts. So you can write code with the assumption that the max depth will be less than 3072 and it will work fine until the heat depth of the universe.

[vbuterin]

Unfortunately there is no easy way to find out in which block a contract was added to the state.

One way to satisfy this constraint is to have a new opcode, CALL', which has the new behavior (ie. it has a 63/64 max but it does not increment the stack depth). Another approach is via the nonce.

[gcolvin]

@vbuterin After re-reading https://blog.ethereum.org/2016/06/19/thinking-smart-contract-security/ I agree with some variation on this idea, depending on the resolution of the discussions above. My preferences are totally trumped by the security advantages. Plus I'm starting to come around on my preferences.

[gcolvin]

@vbuterin A problem remains -- testers go for the theoretical limits, not the practical limits. (So I just went months unable to check in my faster interpreter code until somebody decided we would never really need 2^64 units of gas, let alone the 2^256 actually tested for.) So a maximum depth for testing is needed.

We could choose a cost function that has the stack depth asymptote on some limit. Or we could set a limit in this EIP in addition to your cost function. From your calculations an asymptote or limit of 2048 should last longer than homo sapiens will, keep the testing realistic, and be small enough to preallocate. (And powers of 2 are nice to build machines with, but 3072 is OK too ;-)

[chfast]

From the available options I'm very much for B2. Suggestions:

1. Using test limit of 2^63 gas and the call cost of 700 from Long-term gas cost changes for IO-heavy operations to mitigate transaction spam attacks #150 should give the depth limit of 2094 according to WolframAlpha or 2357 according to @vbuterin formula. It is still over twice as big as the current limit, se we might have issues with stack overflows.
2. I would use the formula g - (g // 64) instead of (g * 63) // 64 to avoid overflows in implementations.
3. Please update the description if anything has become obsoleted by recent attacks and/or Long-term gas cost changes for IO-heavy operations to mitigate transaction spam attacks #150.