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 Solana case shows that even a big blockchain network can experience major outages.

Gas

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.

Hedgehog protocol

Hedgehog’s gas derivatives really seem useful and even necessary for the blockchain network. But who can benefit from it? Who are the prospective users of these contracts? At the risk of sounding rude, I have to note that an average Ethereum user — or any blockchain user for that matter — is not that sophisticated. The protocol’s writers put it quite bluntly but eloquently: “when you ask the end user to hedge their own gas fees, they will tell you to go find your mom”.

Different matter is big players who will find gas derivatives useful for their business. Potential buyers of gas hedging derivatives include but are not limited to:

- Paymasters. In the context of Ethereum, paymaster is a kind of sponsor. It is an entity (a smart contract account) covering gas fees of a transaction executed by someone else. Paymaster is one of the essential components of another Ethereum upgrade, EIP-4337, which is a standard for account abstraction for the Ethereum blockchain. This will hopefully revamp dApp usability and user experience because Paymasters will pay users’ gas fees on their behalf. Since Paymasters have to pay gas fees, sometimes even a hefty premium during network congestion, it is prudent to assume that they will be interested in Hedgehog derivatives. The idea is not dissimilar to that of in other markets. You buy gas derivatives to hedge yourself against gas price spikes.

- Layer 2 solutions. As already briefly mentioned above, these protocols allow to avoid excessive gas fees due to their technology to offload part of computation from the blockchain, thus reducing the demand for the mainnet. But they themselves incur significant operational costs due to their using a lot of gas. For example, Arbitrum, the largest Ethereum Layer 2 solution in terms of Total Value Locked at the time of writing, has spent 20,500 ETH only on base fee alone. With the current price of ETH this is almost $43 million!

Where do these expenses mostly come from? Each transaction on Layer 2 protocols incurs two types of costs: L2 or execution fee, and L1 or security fee. The former is the fee you as a user pay to execute your transaction on a Layer 2 solution. The latter is the fee to publish your transaction on L1, in this case the Ethereum mainnet. That’s why this is sometimes called “mainnet publishing fees”. The diagram below shows the amount of fees in ETH spent monthly by layer 2 protocols while publishing data to the Ethereum mainnet.

Timing of Hedgehog protocol for Layer 2 solutions is close to perfect, I think. If bull market comes, ETH price will surge raising gas fees to heights as well. Considering that more protocols and NFT projects are launched during a bull market in comparison to a bear market, the demand for the Ethereum mainnet will increase drastically which will magnify L2 operational costs. Hedgehog will allow these protocols to decrease their costs and increase profitability.

- Validators. To verify and execute transactions blockchain networks need validators who can be an individual or a group of individuals. However, verifying transactions and adding new blocks to the blockchain require resources which incur costs for validators. That’s why validators are renumerated in the form of gas fees. Though the relationship is not as unambiguous as it may seem, we can say that validators do benefit from high gas fees. They are not a curse for validators, they are a blessing. If this is so, then why would validators even think of hedging gas fees? The same reason why a Bitcoin miner chooses to hedge their position — drop in BTC price will negatively impact your profit margin. In fact, unpredictability of cash flow is one of biggest hurdles for Bitcoin mining industry to attract investors. Now change BTC and miners to ETH and validators. The problem is not high gas fees; it is exactly opposite, low gas fees. Validators need hedging to stabilize their cash flows.

- NFT Marketplaces. It is not surprising to see these players among the potential beneficiaries of gas hedging. This is because minting an NFT due to its resource-consuming nature requires a lot of gas. To improve user experience with NFTs, these marketplaces choose to go fully or partially gas-free. UCOLLEX, a platform to buy physical and digital collectibles and where you don’t need even a crypto wallet, pays gas on behalf of its users. If this trend continues, and I don’t think of any reason why it won’t, NFT marketplaces will have to hedge their gas fees.

Besides hedging, Hedgehog’s gas derivatives can be used for speculative purposes, too. As already mentioned, some events can cause gas price to surge. If there is a popular NFT mint or a chain of DeFi liquidations is expected, you can buy gas derivatives betting on an increase in gas price. In a similar manner, you short these derivatives once an anticipated event happens or doesn’t impact market as expected; this is how you, a true DeFi degen would express the trading idea that gas fees will return to their normal level. I think it won’t be an exaggeration to claim that this would create a new asset class — Ethereum gas price.

Conclusion

High gas fees, especially their surge during certain events, are a big issue for the Ethereum ecosystem. Its unpredictability and volatility do challenge Ethereum’s scalability, further adoption and growth. Being the largest blockchain network, Ethereum doesn’t stay still and constantly evolves. Innovations such as Layer 2 solutions, and Account Abstraction and the increasing popularity address the gas problem, but don’t solve the problem altogether. In fact, as we have explained, these entities themselves can suffer from the volatility of gas fees. Excessive gas fees can eat into their earnings eroding their profitability. A product allowing big players to hedge their gas fees seems almost inevitable for the further growth of Ethereum.

Enter Hedgehog protocol. Hedgehog protocol allows to hedge volatility of and speculate on gas fees on the Ethereum network. It’s a novel idea which has the potential to improve user experience of the largest blockchain network. Many participants of the Ethereum ecosystem, such as NFT marketplaces, paymasters or Layer 2 solutions would benefit from hedging their gas fees. Though V1 of the protocol is focused on Ethereum gas fees, the future plan is to generalize to other on-chain derivatives, such as Bitcoin hashrate, EigenLayer hedging, and even end-user speculation.