Update EIP-4750: align with EOF Megaspec

[pdobacz]

1. Adjust to current spec where the return stack no longer has the stack height
2. Update stack requirement logic
3. ~Update gas to 4 for RETF~
4. RETF from top frame

[eth-bot]

✅ All reviewers have approved.

[github-actions[bot]]

The commit 1932724e8b8753d6016544736a4386e463d41ed3 (as a parent of c21a6241c86fcdd581fdb1f6d4402e09ffd01e42) contains errors. Please inspect the Run Summary for details.

[gcolvin]

I'll offer a high-level comment here: the Motivation section could be a lot stronger and more detailed than just "restricts them from making optimisations" and " improve analysis opportunities." To sell this proposal it must be stronger.

As I've said too often, in the presence of dynamic jumps and the absence of function calls it is currently impossible to traverse the control flow of EVM code in linear time. Which makes many kinds of deploy-time analyses or rewrites of the code subject to DoS. That includes the validations proposed here, translations to more efficiently interpreted code, compilation to machine code, and more.

Dynamic jumps also make some offline static analyses take quadratic time, (and I'm told it makes some take exponential time, and even makes some undecidable.) And it forces some ZK EVMs into parallel execution. And no doubt there many other problems I don't know about.

This is all unsurprising to me and the people dealing with these problems, but I've found it difficult to explain.

But to really get it you have to know

• what a directed graph is,
• what a cyclic directed graph is,
• how to traverse a cyclic graph acyclically, and
• why dynamic jumps make that traversal non-linear.

And given that,

• how code gets represented as a directed control-flow graph,
• how that representation is used in many ways for many purposes,
• including things we want to do at deploy time, and
• why non-linear traversal time makes these things a DoS surface.

And indeed if you haven't studied this stuff you might not get it.

So I don't know if it's worth a brief "tutorial" here or elsewhere, but I'm sure it would be easier than explaining elliptic curve cryptography to me.

[pdobacz]

I'll offer a high-level comment here...

@gcolvin Thanks for posting this, and apologies about not responding earlier. All great points but beyond the scope of this PR, let's have a separate PR if we want to strengthen the Motivation section.

[gcolvin]

@gcolvin Thanks for posting this, and apologies about not responding earlier. All great points but beyond the scope of this PR, let's have a separate PR if we want to strengthen the Motivation section.

Understood. I have the misfortune to have very little time to devote to a topic dear to my heart -- no PR is coming from me. So I just dropped this off while passing through, as it were.