I have been skeptical about Turing complete on chain computation for a long time. Many early proponents took the position that there is no issue because a mechanism such as Ethereum’s gas limits how long a computation can run. They argued that this means computation will always eventually run out of gas and then stop. But the danger of a program not stopping is not the only thing to worry about in a completely open and interconnected computation system. The more pertinent issue is: what will a new smart contract do to the total system state? With Turing complete languages, there is one and only one way of finding out and that is to actually go ahead and run everything.
Another way of saying this is that focusing on the Halting Problem in its most literal sense, as in “Will this program stop?” is too narrow a view of the issue. As I explain in the Halting Problem post from my old Tech Tuesday series, any question such as “will this program output the number 42?” or “will this program ever execute line 42 of its code?” is not answerable in the general case of Turing complete languages. For Blockchains an example question is: Will a new smart contract cause any existing smart contract to misbehave? And gas limits do not help with answering that question. In a system where any contract can refer to any other contract that question is not generally answerable for arbitrary Turing complete contracts other than by executing the system.
Some people have proposed formal verification as an answer. I absolutely believe that smart contracts systems should be built in a way that makes formal verification possible. That will help with some problems, such as detecting and preventing certain kinds of bugs that make possible attacks such as the one that drained one third of The DAO. But formal verification does not get around the problem that even trivial questions about how the system will behave as a whole with a new contract added cannot be generally answered.
So what is to be done? I am partial to having on-chain computation be non-Turing complete. If done correctly this will not impose a huge limitation on the kind of relatively simple and yet hugely helpful computations one would want to carry out as part of smart contracts, such as taking a conditional action. Such an approach would not only make formal verification dramatically easier, but it would make it so powerful that one could in fact answer questions about the impact of new smart contracts on the system as a whole.
Does that mean we have to give up on Turing complete computation entirely for blockchains? No. I believe the right place for Turing complete computation is off-chain. But the blockchain should natively support verification of zero knowledge proof certificates for off-chain Turing complete computation. In this scenario as long as a single off-chain node properly carries out a computation and submits a certificate, then following successful on-chain validation the results of that computation can be used as inputs for smart contracts.
There is no system today that provides this combination of non-Turing complete smart contracts with native support for on-chain validation of zero knowledge proofs for Turing complete off-chain computation. But projects are starting to experiment with and plan for such an approach and I expect to see some version of this become available over the coming year.
