Should Smart Contracts be Non-Turing Complete?

Everyone has their favorite programming language, just as everyone has their favorite shoes or favorite food, but I’m not here to tell you to give up your favorite language (trust me, I would never dream of such a thing). Instead, I want us to take a journey together, a journey will take us through many things. We’ll discuss Turing completeness, evaluate its usefulness in regard to smart contracts, look at alternatives, and hopefully we’ll come to the same conclusion together at the end. Spoiler alert: the conclusion is that giving Solidity a monopoly on smart contracts is a terrible, foolish idea.

So let’s jump right in. (Real quick: TC = Turing Complete and NTC = Not Turing Complete)

Turing Completeness, the briefest explanation

If you don’t have any idea what TC is, I’m going to give you a brief explanation to keep you up to date. If you’ve heard of it before, but don’t quite remember exactly what it is, this will refresh your memory. Let’s jump into it! 

Source: https://dilbert.com/ 

Alan Turing was a mathematician (among many other things) who created a theoretical machine called, of course, the Turing Machine. This mythical machine has access to an infinite amount of RAM and runs using a finite program that determines when it should write, read, and move within its memory. Its programming also dictates under what conditions it should terminate and what it should do next. Programming languages that fit these conditions are known as TC languages.

A quick breakdown of what a TC machine can and can’t do is in order, so let’s look at some examples.

Is complete:

• Has the ability to implement any computable function.
• Always includes a function that won’t terminate by itself.
• Includes a function that, theoretically, could use an infinite amount of memory.

Isn’t complete:

• Doesn’t support loops, recursions, or other goto variants that tend not to terminate on their own.

According to the Tiobe Index, nearly all modern, popular programming languages are TC by default (or have the ability to be TC when needed). The languages that are purposefully NTC are extremely domain specific languages like BicoinScript and Coq (an interactive theorem program that mechanically checks proofs). These languages lack recursion, intentionally, either as a security feature or because they can function without recursion and the developers decided that creating a TC environment was overkill.

Basically, an NTC language is more specialized, while a TC language is a multi-purpose tool that can handle diverse situations. At first you might think, “Well, we should use TC languages for everything, right?” After all, it is flexible, but just as a multitool is a great thing to keep on your belt because it’s handy in many situations, you would probably prefer having the proper tools when repairing something like your car.

Source: http://themetapicture.com/have-you-never-opened-chardonnay-under-fire/ 

To roll with the above analogy, TC languages can be applied more broadly, while NTC languages have specific uses. I don’t know about you, but personally I consider smart contracts to be a specific use case. “But,” you may be thinking, “there are so many different types of smart contracts, and the majority are written in Solidity with no problems.”

Good point, dear reader. I’m glad you brought that up.

Smart Contracts, Solidity, and Turing Completeness

I find that it is always best to turn to the experts in regard to complicated questions, which is what led me to a paper from the Computer Science Institute at the University of Applied Science Ruhr West, in Germany. This paper, aptly titled “Do Smart Contract Languages Need to be Turing Complete?” brings to light a lot of very interesting statistics concerning the journey you and I are on together.

But before we dive too deeply into those stats, let’s quickly examine some of the common flaws that exist because Solidity is a TC language. We have the security flaws that allowed the DAO hack to happen (recursive call exploit), the possibility of attacking poorly implemented smart contracts (reentrancy attacks), and the fact that fees cannot be accurately predicted thanks to recursion (and the Halting Problem). These things only exist because Solidity is a TC language, but it is certainly worth suffering these flaws since we gain so much from TC languages, right?

Right?!

Unfortunately, the folks over at the University of Applied Sciences Ruhr West in Germany tell us a different story. They downloaded 53,575 smart contracts and analyzed the type of coding within each of them. They explain in their paper that “the performed analysis identified the flow control mechanisms used by the extracted smart contracts and assigned each smart contract to a corresponding computability class in order to check for the percentage of smart contracts that actually need a Turing complete smart contract for their implementation and by this answer the raised research question.”

The results were as follows:

• 35.3% – use “for-loops and primitive recursive functions and the problems related to the halting problem associated with this type of function.”
  
  A further breakdown within that 35.3% includes:
• 24.8% “verified contracts use for-loops”
• 3.6% are “contracts that use recursion”
• 6.9% of all analyzed smart contracts made use of a control flow mechanism that usually demands a Turing complete programming language.

There are two ways we can look at this data. Strictly speaking, the last 6.9% (about 3,697 out of 53,575) are the only category that technically require a TC language to function. Even if we are super liberal with our generalizations and assume the whole 35% needs a TC language, is that any better? Heck, I’d go so far as to say that even if half of them required TC it wouldn’t be worth the trade off. So why is Solidity TC?

Solidity’s creation was heavily influenced by JS, C++, Python, and PowerShell, all of which TC languages themselves. To say that Solidity was created as a TC language through 100% intention might be a bit of a stretch. After all, why would you intentionally introduce flaws into your programming language when the benefits aren’t even being utilized? Philip Daian, a PHD student at Cornell, wrote in a rather interesting blog article after the DAO hack that “this was actually not only a flaw or exploit in the DAO contract itself: technically the EVM was operating as intended, but Solidity was introducing security flaws into contracts that were not only missed by the community, but missed by the designers of the language themselves.”

We have other options… right?

Monopolies are bad and stifle growth. Period. We fight against, we support government actions that disband them, yet for some reason we are willing to accept them when it comes to smart contracts? With this in mind, there are two possible futures that I see unfolding in front of us.

Future one, we use our experience with Solidity and grow from it. We expand on Solidity, expand with other languages, like Vyper (an NTC language designed to be used next to Solidity), and continue to ignore the obvious flaws that a TC language brings to the smart contract world.

Future two, we diversify our portfolios. Look, I said earlier that I’m not going to tell anyone to give up their favorite programming language, I lied. The problem in the smart contract community right now is that everyone insists on using Solidity, and I’m just hoping that it’s out of necessity and not desire.

Let’s talk about serious contenders in regard to programming languages in the smart contract world. Let’s talk about Waves’ RIDE.

There are a few reasons why I consider Waves to be a serious contender in this fight, one of the major ones being that Waves showed up, built a system, and has been running it since 2016. Too often you see speculative articles about “this new company” that is going to “revolutionize the space”. When Waves entered the ring, they came in swinging, and they have a showcase of products to show for it.

They’ve got their own blockchain, wallet, and secure browser extension to manage dApp connections, DEX, and now RIDE, their own purpose-designed programming language to build dApps. The reason I bring this up is because Waves is a strong company doing serious things, and this makes their Solidity alternative a significant contender for dApp developers. Honestly, the main problem I have with this company is that the landing page of their website is nauseating, it just... keeps moving.

RIDE is a purposefully NON Turing Complete language that is designed for developers to build smart contracts in a no-nonsense environment. RIDE takes a two-prong approach to this: first, their language provides the basic scripting functionality necessary to create dApps (while at the same time reducing security related errors). Secondly, because the language does not support any recursion or complex loops, it can be easily tested for security flaws.

But the lack of recursion doesn’t just benefit security testing, it also comes into account when calculating gas fees for executing smart contracts on the Waves blockchain. Because it is possible to calculate how long the program should take to run and how complex it will be, prices can be estimated and fees are never charged without executing the dApp (I’m looking at you, Ethereum). 

You may be thinking that because RIDE is purposefully NTC, that it can’t handle the majority of smart contracts being written for the EVM. Remember that study from earlier though, the one with the German Computer Scientists? Less than 7% of tested smart contracts used a loop and needed TC to run.

The real question (the whole purpose of this journey) is: why are we using Solidity, a TC language, when less than 7% of dApps written in Solidity are using its TC features?

That 7% of dApps that require TC smart contracts could theoretically, according to the paper “Self-Reproducing Coins as Universal Turing Machine,” be served by implementing TC features across many different transactions. In their study, they were able to construct a simple TC machine by using a small, specific set of language features that utilized the UTXO (unspent transaction output) model. These transactions were heavily restricted by both input and output transaction states, for safety, and both unbounded and infinite loops were intentionally impossible to trigger in their case. In the same way, RIDE as an NTC programming language can be used to write TC smart contracts without the issues that an underlying TC programming language can bring.

Issues that we are seeing with Ethereum and which are only going to get worse unless they change something major, and since we can see their roadmap for the next few years we know that none of these crucial changes are in the works. They will eventually move to POS instead of POW, and they have Vyper which you can opt to write in if you want increased security. But the bottom line is that TC was a selling point. Heck, Vitalik Buterin even admits in the Ethereum white paper that:

“Turing-incompleteness is not even that big a limitation; out of all the contract examples we have conceived internally, so far only one required a loop, and even that loop could be removed by making 26 repetitions of a one-line piece of code. Given the serious implications of Turing-completeness, and the limited benefit, why not simply have a Turing-incomplete language? In reality, however, Turing-incompleteness is far from a neat solution to the problem.”

Source: https://xkcd.com/329/

So, dear reader, as we have reached the end of our journey together, I ask you this, “What is more important to you as a developer: the ability to write clear, concise code that is automatically resistant to hacks and malicious intent OR the ability to write code in a TC language that is more “neat”?

Ethereum and Solidity undeniably opened the doors to a new world with smart contracts and dApps, but it is long past time we diversify our programming skill sets and break up this monopoly before it takes too strong of a hold. For a developer, switching to a NTC alternative is not such a big leap. In order to make it even easier for you, I’m planning to run you through the entire process and show you specific examples of code in one of my next posts. Stick around because the shift is happening and you have seats in the front row!