How EIP 150 gas cost algorithm works on each stack level?

Question

Based on EIP 150 change the call depth attach.

EIP and EIP-discussion:

Note that with the given parameters, the de-facto maximum call stack depth is limited to ~340 (down from ~1024), mitigating the harm caused by any further potential quadratic-complexity DoS attacks that rely on calls.

On this accepted answer:

With the new rules, the call cannot consume more than 63/64 of the gas of the parent. So if your gas is X, then N CALLs in, it will be max X * (63/64)^n.

[Q] Is this statement correct with the new rules?

Based on my calculations following statement is wrong:

if your gas is X, then N CALLs in, it will be max X * (63/64)^n

because we also need to add cumulative gas-sum till the nth call on the stack.

Hence Till we reach (n-1)th call the parent's gas will be decrease as new gas value: X_n' at each stack level.

For example:

1    => X_1   = X        * (63/64)^n 
2    => X_2   = X_1      * (63/64)^n //X_1 is used instead of X
3    => X_3   = X_2      * (63/64)^n //X_2 is used instead of X
...
N    => X_(N)  = X_(N-1) * (63/64)^n
1022 => X_1022 = X_1021  * (63/64)^n //X_1021 is used instead of X
1023 => X_1023 = X_1022  * (63/64)^n //X_1022 is used instead of X

So Nth call should be something like: X_n * (63/64)^n, where X_n should be much smaller than original X. So gas consumption limit gets much smaller.

Overall, the main question I have is:

[Q] How EIP 150 gas cost algorithm works on each stack level? and how gas consumption limit is affected at each stack level?

Please note that I am not questioning the answer, I just want to understand what should be correct.

Thank you for your valuable time and help.

Answer 1

[Q] Is this statement correct with the new rules?

Yes. The gas available at each stack depth certainly won't exceed this amount.

[Q] How EIP 150 gas cost algorithm works on each stack level? and how gas consumption limit is affected at each stack level?

Take a concrete example.

Let's say a contract is called with 4,000,000 gas. The maximum gas it can pass to any contract it calls is 4,000,000 * 63 / 64 = 3,937,500. This is the gas available to the contract at stack-depth 1.

Now the contract at stack-depth 1 calls another contract, the maximum gas it can pass down is 3,937,500 * 63 / 64 = 3,875,977. This is the gas available to the contract at stack-depth 2, and is 4,000,000 * (63/64)^2.

The contract at stack depth 2 calls another contract. It can pass down a maximum of 3,875,977 * 63 / 64 = 3,815,415 gas to stack depth 3, which is 4,000,000 * (63/64)^3.

And so on. At each stack depth N, a maximum of X * (63/64)^N gas is available to the contract at that stack-depth, where X is the initial gas in the calling transaction, and the top level is 0.

If this were the only mechanism, then the total possible stack depth you could reach when starting with 4,000,000 gas would be log(4,000,000/700)/log(64/63) = 549. However, because making the contract calls uses gas each time (700 gas, this is where the 700 comes from in this calculation: you need at least 700 gas to make another call), the actual maximum depth you can reach is somewhat less than this (hence the ~340 from the EIP when starting with 5.5 million gas).

It actually looks like this more precisely, taking into account the cost of 700 gas for the contract call:

Stack depth 0: X gas available
Stack depth 1: (X - 700) * 63/64 gas available
Stack depth 2: ((X - 700) * (63/64) - 700) * (63/64) gas available
Stack depth 3: (((X - 700) * (63/64) - 700) * (63/64) - 700) * (63/64) gas available
...
Stack depth N: X * (63/64)^N - 700 * 63*(1-(63/64)^N) gas available (after simplifying the expression)

The last line is calculated by noticing that each line simplifies as follows.

Stack depth N: X * (63/64)^N - 700 * [(63/64) + (63/64)^2 + ... + (63/64)^N]

The part in square brackets is then the sum of a geometric progression, which by the well-known formula sums to (63/64) * (1 - (63/64^N) / (1 - (63/64)) = 63 * (1 - (63/64)^N)