New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Substitute call stack limit with child gas restriction #114

Open
vbuterin opened this Issue Jun 16, 2016 · 15 comments

Comments

Projects
None yet
9 participants
@vbuterin
Collaborator

vbuterin commented Jun 16, 2016

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 109 (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(109 / 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

This comment has been minimized.

Contributor

chriseth commented Jun 19, 2016

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

This comment has been minimized.

Collaborator

vbuterin commented Jun 20, 2016

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

This comment has been minimized.

Contributor

chriseth commented Jun 20, 2016

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

This comment has been minimized.

Collaborator

gcolvin commented Jun 20, 2016

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

@gcolvin

This comment has been minimized.

Collaborator

gcolvin commented Jun 21, 2016

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

This comment has been minimized.

Collaborator

gcolvin commented Jun 21, 2016

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 comment has been minimized.

Collaborator

nicksavers commented Jun 21, 2016

... 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

This comment has been minimized.

eth1au commented Jun 21, 2016

@vbuterin

This comment has been minimized.

Collaborator

vbuterin commented Jun 23, 2016

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

This comment has been minimized.

Collaborator

vbuterin commented Jun 23, 2016

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

This comment has been minimized.

Collaborator

gcolvin commented Jun 28, 2016

@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

This comment has been minimized.

Collaborator

gcolvin commented Jul 7, 2016

@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

This comment has been minimized.

Contributor

chfast commented Oct 11, 2016

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 #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 #150.
@chriseth

This comment has been minimized.

Contributor

chriseth commented Oct 12, 2016

@chfast I think if you actually allow 2^63 gas, we have a lot of other problems. I would say that voting the gas up to such areas while knowing that some miners cannot cope with such a resource usage can be seen as a 51% attack, so I would not include this as something we have to guard against.

I would prefer a stack depth around 1024 (unless this number was deemed unrealistic in a recent analysis) at the current magnitude of the block gas limit.

@chfast

This comment has been minimized.

Contributor

chfast commented Oct 12, 2016

I was thinking about the limit we test for. We can lower it to 2^62 or 10^9. It should be a number we never plan to reach in the block gas limit.

With the limit of 5.5M the call depth will be ~63 (needs verification). Is it fine?

@lght

This comment has been minimized.

lght commented Nov 8, 2017

I'm really interested in this area for static analysis and testing, is changing the call stack to child gas limit still a thing?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment