Ethereum Gas and The Turing Machine
Gas is the unit that measures the amount of computational effort needed to execute specific operations on the Ethereum network.
The Halting Problem
In his highly influential 1936 paper On Computable Numbers, with an application to the Entscheidungsproblem , Alan Turing defined a mathematical model of computation that describes an abstract machine manipulating symbols on a tape of infinite length according to a table of rules. This is called a Turing machine, and any machine or software that matches this description is called Turing complete. Given any arbitrary problem, there is no generalized algorithm which can determine whether the problem will stop at some time or continue running forever. This is called the Halting Problem.
Why does Ethereum need Gas?
Bitcoin has no gas. The concept of gas came with Ethereum because it tries to expand on the functionality of Bitcoin. Bitcoin has just a very basic use of storing value and transferring it. Ethereum aims to have complex dapps(decentralized apps) running on it powering a full fledged digital block chain based economy. The Ethereum Virtual Machine ( one canonical state comprising of all the connected nodes ) is a Turing complete machine, and thus suffers from the halting problem. However unlike your computer or smartphone, which you can just restart if you by mistake run an infinite loop program, one cannot just ‘restart’ the EVM. A malicious smart contract can be so designed that it keeps running forever when a node tries to validate it, because the EVM cannot know whether it will halt or not until after it has executed it. This amounts to a DDoS attack.
Enter gas. With every transaction you make on Ethereum, every smart contract you send on the blockchain to run, you have to send additional ether(ETH) than required. The additional ether is earmarked for gas fees. Your contract will only be fully executed if it has the required amount of gas, otherwise its execution will stop when the gas runs out. This cleverly sidesteps the limitation of the Halting Problem. Ethereum uses gas to allow Turing complete computations while limiting the resources they consume.
How does gas work?
As the EVM executes a smart contract, it carefully accounts for all the instructions ( computations, data access, etc.) in the contract. All these instructions have pre determined price in terms of gas. Gas is not bought from any exchanges. Instead, when a transaction triggers a smart contract, along with the transaction we send extra ether earmarked for gas, along with an acceptable gas price. Gas prices are measured in gwei ( 10^-9 ETH) . Suppose I’m sending you 1 ETH, and setting a limit of 21000 gas units. If the cost of gas currently is 200gwei, I need to send 21000*200=4200000 gwei, or 0.0042 additional ETH . So I’ll be sending 1.0042 ETH for you to receive 1 ETH. If that amount of gas is insufficient, the transaction will not execute. If it required less gas than I’ve sent, the excess ETH will be refunded to me.
High gas costs
One of the problems plaguing Ethereum as it tries to scale is its high gas costs. Gas prices can go up for a variety of reasons. One, the miners validating the transaction blocks prioritize transactions willing to pay the highest gas fees. This ends up with users trying to outbid each other, thus driving up costs. Two, as the dapps ( decentralized apps) on Ethereum get more and more complicated, they need more and more gas to execute.
Ethereum is working on these issues, especially with Eth2 Serenity. It is working towards moving on from Bitcoin’s Proof of Work consensus algorithm which it currently uses, to a Proof of Stake algorithm, which should reportedly cut down gas costs by 99% . Layer 2 scaling is the solution that is currently being deployed to cut down gas costs. This basically allows you to use the robust decentralized Ethereum mainnet, while handling transactions off Ethereum on some third party blockchain with faster speeds and lower costs.
