Bit(s) of theoretical computer science?—?on Turing-completeness
If you have been interested in the theoretical foundations of blockchain?—?and I would say that even if you haven’t?—?you have heard of Ethereum being Turing-complete. What does this exactly mean? Turing-completeness was defined by the greatest British mathematician Alan Turing. Without going into the depths of theoretical computer science and at the risk of simplifying of a complex subject, we can say that a device (or a language or a machine) being Turing-complete implies that it can execute almost any computational task with correct, unambiguous instructions given that this machine has runtime and sufficient computing power. Most modern programming languages, e.g., Java, Python, C++ are Turing-complete.
Unlike the first blockchain network, Bitcoin, whose scripting language intentionally was designed to be Turing-incomplete because unnecessary complexity would pose challenges to the network, Ethereum is Turing-complete. Though Turing-completeness may seem as a nice feature to have, in public blockchains it can be challenging due to the so-called “halting problem” (yeah, yet another computer science-related term).
In layman’s terms, the halting problem can be explained through the analogy. Suppose your teacher says: “”If you always listen to me, ignore me. Otherwise, always listen to me”. It is not hard to imagine that you will follow these instructions to infinity assuming you are immortal (quite an assumption I’d say). If you listen to your teacher, then you have to ignore him as per their request. If you ignore him, you have to listen to him. Which means that you have to ignore him which means that you should listen to him and so on. The problem will never halt. Halting problem is the same thing with the only difference that you in the example are replaced with a computer. That is, computer will never know if any given program halts or not without running it. You cannot predict whether a given program will end or not by simulating on a computer. Therefore, in Turing-complete systems there can always be a program that will run in infinite loop without ever terminating.
Ethereum and halting problem
Now back to blockchains, specifically to Ethereum. There are many programs that run on Ethereum which we call smart contracts. There can always be a program, either by accident or by design, that can run forever on Ethereum consuming the blockchain’s resources and congesting the network. Ethereum Virtual Machine, a huge computational engine on which Ethereum runs cannot predict whether a smart contract will end or how long it will run. So, Turing-completeness gives the system flexibility but it also poses computational challenges to the system. A blockchain network, unlike an unresponsive printer, cannot be easily turned off and turned back on again though case shows that even a big blockchain network can experience major outages.
To address this challenge Ethereum introduced the concept of gas. Every transaction on the Ethereum network has gas costs associated with it. Think of gas as the price of executing a transaction on Ethereum. You want to send a token, or create a contract? No problem, just pay your gas fees. You can think of gas as the virtual fuel required to operate the blockchain network. Gas fees are typically expressed in Gwei, a term referring to one billionth of one Ether token (ETH). One Gwei = 10–9 or 0,000000001 ETH.
Among blockchains, Ethereum is notoriously known for its high gas fees. This is not surprising. Ethereum is the largest blockchain networks in terms of daily transactions.
As more and more users start using the network, high demand is being translated into high gas fees. For example, activity on the Ethereum network surged when Yuga Labs, the creator of the famous Bored Ape Yacht Club, launched Otherside NFTs. Since many enthusiasts wanted to mint an Otherside NFT, gas fees spiked reaching 6,000 gwei. To understand why these fees are considered super high, I have to note that median gas price is around 32 at the time of writing.
And to prove that I don’t cherry-pick showing only one day’s chart which happens to be low, here is the chart of gas price dynamics within the most recent 90 days. It barely exceeded 40.
Though the popularity of the blockchain network is a very decisive factor explaining high gas fees, it is by no means the only variable. Recall that gas is related to computational resources; that is, the more computing power a transaction consumes, the more expensive it will be. Interactions with a smart contract or minting an NFT do require do have a high transaction complexity which leads to high gas fees. We shouldn’t ignore the economic motivations of major network participants, i.e., validators and miners, who in order to increase their rewards prioritize transactions with high fees.
What can be done about excessive gas fees?
If gas fees can at times be prohibitively expensive, how does Ethereum address the problem? There is no a direct solution to the problem on the Ethereum network itself as such. Even the highly anticipated Merge event, which completed transaction to proof-of-stake (PoS) and made ETH a less inflationary token, didn’t decrease gas fees. Sure, there are ways to pay less for gas fees:
- Simulate the transaction. By simulating the transaction you want to execute you can get an understanding of how much gas your transaction will spend. Several tools, such as Defi Saver allows you to do it.
- Be patient and choose the right time. As the chart above (Median Gas Prices, by hour) makes it clear, gas price is not constant during the day. You can postpone your transaction to the moment where gas price tends to be low.
- Using Layer 2 solutions when possible. Layer 2 solutions, e.g., Arbitrum and Optimism were designed to address the scalability of the Ethereum network. Some of these solutions, namely zero-knowledge rollups transport data off-chain which means that the frequency of the data relevant to smart contracts decreases. As a result, less computational power is deployed and gas fees drop.
But none of these strategies enables hedging against gas fees. This is what Hedgehog protocol aims to do. But why hedging, you may ask? Hedging reduces unpredictability and negative effects of volatility of gas fees.
The Ethereum Foundation, a non-profit organization that supports the Ethereum ecosystem, understands the importance of the problem. High gas fees not only lead to bad user experience and thus hinders its global adoption, it also reduces network’s capacity. To address the issue, in August 2021 an upgrade called EIP-1559 happened. It changed the way how Ethereum treats and processes gas fees. Prior to this upgrade there was a single gas price. Under EIP-1559 gas fees are divided into two types of charges:
- Base fee. It is a standard charge paid by all users. It is not set by end users but by the network itself based on the network traffic. All ETH tokens used to pay base fee are subsequently burnt which decreases the supply of the Ether token which can positively impact its price in the long run. The reason why these tokens are burnt is that every time base fee and priority fee are generated, new ETH should be minted which increases its supply; you cannot do anything with priority fees since they are paid directly to validators (explained below). So, the only option is to burn ETH tokens used to pay base fee to offset the inflationary pressure on the token.
- Max priority fee, more informally known as a Tip. This is an optional fee which is determined by a user and which is directly paid to miners to incentivize them to include user’s transaction into a block.
EIP-1559 helps with the unpredictability of the previous fee mechanism and can prove useful in decreasing fee spikes because of its algorithmic base fee setting. Moreover, it decreases manipulation of fees by miners. Nonetheless it doesn’t solve the problem of high gas price, especially gas spikes during network congestion.
