Ethereum Virtual Machine is Turing-complete

Travis Patron asks in Coindesk “What’s the Big Idea Behind Ethereum’s World Computer?”  His answer is, basically, that “the Ethereum virtual machine is Turing-complete”. (See the official whitepaper.) I’ll take their word for this. Technically, that means it is logically equivalent to a Turing machine, and therefore can compute any “computable function”. It is, in short, able to do what you could do with any conventional computer and programming language.

My computation theory is quite rusty, but my recollection is that Turing complete languages are both good and bad. Capable of expressing an immense array of algorithms, and also capable of delivering every bug known to humanity. They are also very, very difficult to program correctly. (It’s not that difficult to program a computer, but it’s nearly impossible to do so without error.)

Nevertheless, the EVM is capable of expressing very complex computations, and of very complex code (even for simple computations). The EVM has “jump” statements which enable loops and alternative paths through the code, and “contracts can call other contracts, potentially allowing for looping through recursion”. (Yoiks!) “Smart contracts” may also rely on external services and data to report an external event, such as “delivery by a given date”.

The practical upshot is that, even without infinite loops, EVN contracts can still have serious logical bugs that are difficult to detect before or during execution.

Considering “contracts”, we have to remember that human language is not Turing complete, which is part of why computers have so much trouble dealing with natural human speech and text. Human thinking and speech is ambiguous, messy, and illogical. The EVM cannot express any possible contract, because the EVM cannot express any possible human thought.

In fact, the EVM actually restricts the computation in ways that makes it not  a simple Turing machine. It uses the Ethereum blockchain as write-once memory (which eliminates many kinds of errors and attacks), but I’m sure that they simulate read-write memory when they need to, so that’s not much of a win.

The big restriction is that the EVM limits the instructions a computation may use, effectively putting a time and space limit on the Turing machine. This is a common tactic, especially in “real time” control systems which must not crash (e.g., while the aircraft is flying). Ethereum calls this “ether” (naturally) or “gas”, and use it to prevent infinite loops or recursions—one of the all time favorite goofs for programmers. They add a cool twist by associating this “gas” with a cryptocurrency, so you have to “insert another nickel for the next 3 minutes, please”.

These features make a language somewhat “fail safe”, which is what EVM is aiming to do. If you are going to ask every node to run your program, it is very important that we be confident it isn’t going to mess up our system. This, by the way, was the concept for the Java Virtual Machine, C#’s manage execution, and other languages for the Internet era.

Unfortunately, being a Turing complete language is scarcely perfect, and arguably is a bad fit for the intended application, “smart contracts”.

First of all, many important concepts cannot be computed by a Turing machine. This is one of the founding pillars of the “science” in Computer Science. Sadly, many things that you want in a “smart contract”, even something as simple as what day it is, or whether a package as been delivered, are not “computable”. That is why “smart contracts” almost always depend on external services to act as “oracles”. Any computation with external IO from such an oracle is, well, off the map of Turing machines.

Second, the programs we can write are often ambiguous or just plain wrong, because it is very difficult to understand any moderately complex Turing machine. Even if the EVM executes the program perfectly on each node each time, it may well be the wrong program.

This is particularly important to keep in mind in the case of the imagined “autonomous” contracts between parties. Whatever the logic of the executable contract may be, it is unlikely that all the parties understand it in the same way. If a contract is even moderately complicated, it is very possible that no one actually understands it. What this means is that only the most trivial “contracts”, e.g., ‘X pays N to Y’, are in any way “transparent”. Anything more complex is impossible to really understand.

The bottom line is that EVM in and of itself offers very little new capability that you can’t get with any number of existing programming or scripting languages. And the fact that it is “Turing complete” (at least sort of) is a two edged sword. Powerful enough to be useful, and powerful enough to be dangerous.

Whether the overall system is useful remains to be seen.  Much depends on the rest of the system (SDKs, debugging tools, coding environments, etc.)

 

Cryptocurrency Thursday

5 thoughts on “Ethereum Virtual Machine is Turing-complete”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s