Gas Mechanism

Ethereum’s metering system: every EVM opcode has a fixed gas cost; a transaction’s sender prepays gas, execution halts when the limit is reached, and miners collect the fees regardless. The stated purpose (Ethereum yellow paper) is to “sidestep the inevitable issues stemming from Turing completeness.”

House on Rock - LangSec in Ethereum Classic argues this conflates a resource bound (non-semantic, decidable) with a safety guarantee (semantic, undecidable per Rice’s Theorem). Gas can show that a contract eventually halts; it cannot show that it behaves correctly. Worse, the accounting is itself adversarial: attackers are rewarded for gas-griefing or out-of-gas-reverting, and honest authors face perverse pressure to remove runtime sanity checks (Perverse Incentives) because conditionals cost gas.

Tags

#ethereum #smart-contracts #gas #langsec

Perverse Incentives

Economic structures that reward the opposite of their ostensible aim. The classic form is the “cobra effect”: a bounty intended to reduce cobra populations induces breeding-for-bounty. In systems design, perverse incentives arise when a metering or policing mechanism becomes itself an adversarial game with direct monetary reward for gaming it.

Example from House on Rock - LangSec in Ethereum Classic: the Gas Mechanism creates a perverse incentive for contract authors to remove runtime sanity checks — every conditional costs gas, so defensively-written contracts lose on cost to recklessly-written ones. The policing mechanism itself erodes the behaviour it was supposed to encourage.

Rice’s Theorem

A foundational result in computability theory (Henry Gordon Rice, 1951–53): every non-trivial semantic property of the partial function computed by a program is undecidable. Source paper: Classes of Recursively Enumerable Sets and Their Decision Problems. “Non-trivial” means the property holds for some computable functions but not others; “semantic” means it depends on the input/output behaviour, not on the syntactic form of the program.

Put differently: you cannot in general decide, by inspecting a program, whether it belongs to any interesting class defined by what it does. Halting is one such property (Halting Problem), but so is “produces output X on input Y,” “terminates for all inputs,” “implements function f,” “contains no unreachable states,” and so on.

Rice’s theorem is the formal frontier against which static-analysis, verification, and capability-bounding claims must be measured. Any tool promising to decide a non-trivial semantic property on arbitrary programs is — by Rice — either restricting the program class (e.g. Finite-state Grammars, typed or total subsets) or approximating (sound-but-incomplete analyses). Whole research programs — LangSec, Formal Verification, Static Analysis, Weird Machine — are organised around this constraint.

Concrete implication cited in House on Rock - LangSec in Ethereum Classic: Ethereum’s gas mechanism cannot “sidestep Turing completeness” to deliver a safety guarantee, because safety is a semantic property and Rice’s theorem makes semantic properties of arbitrary programs undecidable. Gas is a resource bound (non-semantic, decidable) masquerading as a safety property (semantic, undecidable).

Computability lineage

graph TD G["Gödel (1931) Incompleteness (Principia)"] --> GR["Gödel (1934) General Recursive Functions"] C["Church (1936) An Unsolvable Problem of Elementary Number Theory"] --> K["Kleene (1936) On Notation for Ordinal Numbers"] GR --> K T["Turing (1936) On Computable Numbers"] --> HALT[[Halting Problem]] C --> HALT K --> RE["Kleene (1943) Recursive Predicates and Quantifiers"] RE --> POST1["Post (1944) Recursively Enumerable Sets"] POST1 --> POSTPROB["Post's Problem"] RE --> MYH["Myhill (1952) On Definable Sets of Positive Integers"] POST1 --> RICE["Rice (1953) Classes of R.E. Sets and Their Decision Problems"] HALT --> RICE RICE --> RT((Rice's Theorem)) RT --> LS[[LangSec]] RT --> FV[[Formal Verification]] RT --> SA[[Static Analysis]] GR -.equivalence.- T C -.equivalence.- T

Summary

A LangSec critique of Ethereum aimed at the Ethereum Classic community, framed around the parable of the wise and foolish builders and Philip K. Dick’s “reality is that which, when you stop believing in it, doesn’t go away.” Patterson argues Ethereum was built on sand — an ad-hoc, non-executable yellow-paper semantics; a hand-rolled Solidity parser; a test suite with no coverage for delegatecall or invalid opcodes; a design culture that scorned formal methods until hundred-million-dollar losses forced the issue.

The central technical argument is that the gas mechanism does not do what the yellow paper claims it does. Gavin Wood’s stated purpose — “sidestep the inevitable issues stemming from Turing completeness” — confuses a resource bound (a non-semantic, decidable property) with a safety guarantee (a semantic property that Rice’s theorem makes undecidable in general). Gas cannot show a contract “does nothing malicious”; it can only show it eventually halts. Worse, gas creates an adversarial economic game with direct monetary reward for tricking the accounting, and a perverse incentive for honest developers to omit runtime sanity checks because conditionals cost gas.

Patterson’s prescription for Ethereum Classic: standardise on KEVM (an executable operational semantics in the K framework), fix the VM test suite’s gaps, build languages that don’t hide implicit behaviour (method visibility defaults, fallback methods, delegatecall as naked eval), and invest in developer tools — IDEs, live debuggers, verification — that surface what a contract can actually do. “Code is law” requires the meaning of the code to be unambiguous, executable, and visible.

Key Ideas

Rice’s theorem bounds what gas can mean. Non-trivial semantic properties of arbitrary programs are undecidable; resource bounds are non-semantic. Gas therefore cannot sidestep Turing-completeness-induced safety problems, contrary to the yellow paper.

Gas as adversarial game. The accounting is an attack surface, not a safety property; attackers are paid to win. Honest contract authors are weakly pushed toward removing checks to keep gas costs competitive.

LangSec programmer–machine contract. Inputs must have a formal grammar; two implementations of the same spec must accept/reject identical inputs; semantics must be executable so claims about behaviour can be verified mechanically.

Ad-hoc semantics breeds consensus failures. When the yellow paper and cpp-ethereum disagree, cpp-ethereum wins — the denotational semantics is decorative. Discrepancies between clients have already caused real Ethereum consensus failures.

Test suites are part of software design. Official VM tests have no coverage for invalid opcodes or delegatecall — the exact instruction at the heart of the Parity multisig hacks. “VM tests” is false advertising; downstream VM implementations inherit the blind spot.

Case studies of processing-fluency failure.

DAO: mutual recursion across a defender/attacker code boundary, missed in reviews because reviewers examine functions one at a time (cf. Leveson: accidents emerge from interactions).
Hacker Gold: =+ typed instead of += — a hand-rolled recursive-descent parser caught nothing; a Bison grammar would have surfaced a shift/reduce conflict.
Parity multisig (July 2017): fallback method × delegatecall × public-by-default visibility = naked eval on attacker-controlled payload; $31M drained, $150M saved only by counter-theft.
Parity multisig (Nov 2017): library contract re-initialised by an outsider then suicided, locking $153M in wallets whose code had vanished — “left-pad for multi-million-dollar table stakes.”

KEVM (K framework operational semantics) gives Ethereum an executable semantics; generated interpreter ~20× slower than cpp-ethereum but usable, and supports reachability-based proof of safety/liveness claims.

Cognitive-science constraint. Miller’s 7±2 bounds how much implicit state a programming language can demand before human reasoning fails. Solidity’s implicit defaults (public methods, fallback dispatch, implicit conversions) exceed that budget.

“Worse is better” is unconscionable in a financial system. Sacrificing correctness and completeness to ship first transfers the cost of undefined behaviour onto users.

Connections

Making Smart Contracts Smarter — same semantic gap diagnosis; OYENTE is the symbolic-execution complement to Patterson’s formal-semantics prescription.

Formalise Blockchain Interoperability Patterns — companion move: formalise what was informal.

Security Applications Of Formal Language Theory — the Sassaman/Bratus/Patterson LangSec manifesto this talk operationalises for smart contracts.

The Halting Problems of Network Stack Insecurity — parallel argument that parser/semantics weakness is the root cause of whole vulnerability classes.

Exploit Programming - From Buffer Overflows To Weird Machines — “weird machines” framing applies directly to contracts driven off-spec via delegatecall.

PKI Layer Cake - Kaminsky Patterson Sassaman — Patterson’s earlier demonstration that grammatical discrepancies between implementations are exploitable (SSL CA forgery); same mechanism, different domain.

A Language-Based Approach To Prevent DDoS — language-theoretic remediation as a general pattern.

Operational Semantics, Denotational Semantics, EVM, Solidity, TheDAO, Reentrancy — background concepts.

An Unsolvable Problem of Elementary Number Theory — Church 1936; LangSec’s undecidability heritage behind the Rice’s-theorem argument against gas-as-safety.

Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I — Gödel 1931; the incompleteness ancestor of the semantic-limit arguments.

Gas Mechanism

Tags

Backlinks