Turing Completeness and Implications

In 1936 Alan Turing created a mathematical model of a computer (Turing machine) consisting of a state machine that manipulates symbols by reading and writing them on sequential memory (resembling an infinite-length paper tape).

  • With this construct, Turing went on to provide a mathematical foundation to answer (in the negative) questions about universal computability, meaning whether all problems are solvable.

Turing proved that there are classes of problems that are uncomputable. Specifically, he proved that the halting problem (whether it is possible, given an arbitrary program and its input, to determine whether the program will eventually stop running) is not solvable.

  • He proved that you cannot predict whether a program will terminate without actually running it.
  • We have to actually go through with the execution of the program and wait for it to finish to find out. If it is going to take forever to execute, we will have to wait forever to find out.

A system of data-manipulation rules (such as a computer’s instruction set, a programming language, or a cellular automaton) is said to be “Turing complete” or “computationally universal” if it can be used to simulate any Turing machine.

  • Such a system is called a Universal Turing machine (UTM).
  • Modern printers are Turing complete and can be given files to print that send them into a frozen state.

Turing completeness is very dangerous, particularly in open access systems like public blockchains, because of the halting problem.

The fact that Ethereum is Turing complete means that any program of any complexity can be computed by Ethereum. Every participating node (client) must validate every transaction, running a local copy of the EVM to validate contract execution called by the transaction. But as Turing proved, Ethereum can’t predict if a smart contract will terminate, or how long it will run, without actually running it (possibly running forever, effectively being a DoS attack). In a world computer, a program that abuses resources gets to abuse the world’s resources.

  • Ethereum acts like a single-threaded machine, without any scheduler, and so if it became stuck in an infinite loop this would mean it would become unusable.

Ethereum needs to find a way to constrain the resources used by a smart contract even if it cannot predict resource use in advance.

Gas

Ethereum introduces a metering mechanism called gas.

  • As the EVM executes a smart contract, it carefully accounts for every instruction (computation, data access, etc.).
    • Each instruction has a predetermined cost in units of gas.
    • Ethereum must account for every computational step performed by transactions and smart contract code execution.
  • There is also a gas cost to using EVM memory and for storing data in a contract’s on-chain storage.
    • Bitcoin’s transaction fees only take into account the size of a transaction in kilobytes.
  • When a transaction triggers the execution of a smart contract, it must include an amount of gas that sets the upper limit of what can be consumed running the smart contract.
    • Gas can only be purchased as part of a transaction, and can only be bought with ether.
  • If the EVM reaches the end of execution successfully, without running out of gas, the gas cost used is paid to the miner as a transaction fee.
    • Any unused gas is refunded back to the sender of the transaction.
  • The EVM will terminate execution if the amount of gas consumed by computation exceeds the gas available in the transaction.
    • If after a prespecified maximum amount of computation has been performed, the execution hasn’t ended, the execution of the program is halted by the EVM.
    • This makes the EVM a quasi–Turing-complete machine: it can run any program you feed into it, but only if the program terminates within a particular amount of computation.

Gas is a resource constraining the maximum amount of computation that Ethereum will allow a transaction to consume. If the gas limit is exceeded during computation, the following series of events occurs:

  • An “out of gas” exception is thrown.
  • The state of the contract prior to execution is restored (reverted).
  • All ether used to pay for the gas is taken as a transaction fee paid to the miner; it is not refunded.

When performing a transaction, the sender specifies the gas price they are willing to pay (in ether) for each unit of gas.

  • When constructing a new block, miners on the Ethereum network can choose among pending transactions by selecting those that offer to pay a higher gas price.
  • It’s important to match gas cost to the real-world cost of resources.
  • Gas cost is the number of units of gas required to perform a particular operation.

Ethereum encourages the deletion of used storage variables and accounts by refunding some of the gas used during contract execution.

  • There are two operations in the EVM with negative gas costs:
    • Deleting a contract (SELFDESTRUCT) is worth a refund of 24,000 gas.
    • Changing a storage address from a nonzero value to zero (SSTORE[x] = 0) is worth a refund of 15,000 gas.
  • To avoid exploitation of the refund mechanism, the maximum refund for a transaction is set to half the total amount of gas used (rounded down).

The block gas limit is the maximum amount of gas that may be consumed by all the transactions in a block, and constrains how many transactions can fit into a block.

  • If a miner tries to include a transaction that requires more gas than the current block gas limit, the block will be rejected by the network.

Gas Optimization

Angles:

  • Base gas price; priority gas price.
  • The gas costs of constant and immutable variables are much lower.
  • The low-level calls which operate on addresses rather than contract instances (i.e. .call(), .delegatecall(), .staticcall(), .send() and .transfer()) do not include this check, which makes them cheaper in terms of gas but also less safe. They break the type-safety of Solidity.
  • Using a custom error instance will usually be much cheaper than a string description, because you can use the name of the error to describe it, which is encoded in only four bytes.
  • When using elements that are smaller than 32 bytes, your contract’s gas usage may be higher. This is because the EVM operates on 32 bytes at a time. Therefore, if the element is smaller than that, the EVM must use more operations in order to reduce the size of the element from 32 bytes to the desired size.
  • It might be beneficial to use reduced-size types if you are dealing with storage values because the compiler will pack multiple elements into one storage slot, and thus, combine multiple reads or writes into a single operation.
    • If you are not reading or writing all the values in a slot at the same time, this can have the opposite effect, though: When one value is written to a multi-value storage slot, the storage slot has to be read first and then combined with the new value such that other data in the same slot is not destroyed.
  • Struct field ordering.

Recommended practices:

  • Avoid dynamically sized arrays
    • Any loop through a dynamically sized array where a function performs operations on each element or searches for a particular element introduces the risk of using too much gas.
  • Avoid calls to other contracts
    • Calling other contracts, especially when the gas cost of their functions is not known, introduces the risk of running out of gas.
    • Avoid using libraries that are not well tested and broadly used.
  • Estimating gas cost
    • gasEstimate
    • It is recommended that you evaluate the gas cost of functions as part of your development workflow, to avoid any surprises when deploying contracts to the mainnet.

References

  • Mastering Ethereum by Andreas M. Antonopoulos and Dr. Gavin Wood (O’Reilly). Copyright 2019 The Ethereum Book LLC and Gavin Wood, 978-1-491-97194-9