A Step Towards Efficient Reduction of Ethereum’s Turing-Completeness
摘要
A blockchain’s expressive power is ultimately equivalent to that of its underlying low-level language and virtual machine. The most popular blockchains are designed as either Turing-incomplete platforms, which intentionally restrict a blockchain’s expressive power, or as Turing-complete systems with no theoretical restrictions to lower abstraction levels. Statistics show that 64% of applications on Ethereum—a Turing-complete blockchain—do not require a Turing-complete execution environment. On the other hand, none of the existing Turing-incomplete blockchains possess the expressive power to host those applications. In this paper, we propose an approach to creating a blockchain environment that represents the middle ground between the two extreme blockchain design approaches described. Instead of building a restrictive Turing-incomplete system from the ground up, as existing blockchains do, we take a reverse approach by reducing the Turing-completeness of Ethereum. Specifically, we introduce a more restrictive and secure way of creating loops in Ethereum’s low-level language. To enable these restrictions, we alter both Ethereum’s low-level language and its virtual machine architecture. As a result, these alterations make it highly unlikely, if not impossible, for infinite loops to occur and reduce the risk of unintentionally writing long-lasting finite loops. Furthermore, by choosing to reduce Ethereum, rather than building a new solution from scratch, we preserve the majority of Ethereum’s high expressive power even after introducing restrictions. We show that the expressive power of our altered version of Ethereum is at least equivalent to that of the set of primitive recursive functions, which is highly expressive despite its Turing-incompleteness.