An Approach to Efficient Reduction of Ethereum's Turing‐Completeness

ABSTRACT A blockchain's expressive power is determined by its low‐level language and virtual machine. Most blockchains adopt either Turing‐incomplete designs, which sacrifice expressiveness for safety, or Turing‐complete architectures, which offer flexibility at the cost of increased risks. Research reveals that at least 64% of Ethereum applications do not require a Turing‐complete execution environment. However, existing Turing‐incomplete blockchains lack the expressiveness to support those applications. This paper proposes a middle path that bridges this gap by reducing the Turing‐completeness of Ethereum rather than designing a Turing‐incomplete system from scratch. Our approach introduces a restricted loop construct in Ethereum's low‐level language and modifies its virtual machine architecture to eliminate infinite loops and mitigate risks of long‐lasting finite loops. These changes preserve most of Ethereum's expressive power while restricting it to the set of primitive recursive functions, which is highly expressive despite its Turing‐incompleteness. To evaluate the impact of these changes, we analyzed 49,578 production smart contracts and found that the additional memory required is minimal, amounting to only a few dozen bytes.