Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.
Sign up to join this community
Can somebody explain to me why the Bitcoin scripting system is purposefully not Turing-complete? To make malicious programs difficult to develop (I guess)? Or because it was difficult to make it Turing-complete?
Bitcoin uses a scripting system for transactions. Forth-like, Script is simple, stack-based, and processed from left to right. It is purposefully not Turing-complete, with no loops.
Retrieved from: https://en.bitcoin.it/wiki/Script.
As others have said, there is no real need for Bitcoin scripting to be more complex than it is, as its complexity is more than enough for its intended applications; but the main reason is that not allowing some features (such as loops) in a language makes it completely deterministic: you can know for sure when and how a given program will end; you can't f.e. have infinite loops if you don't have loops in the first place, thus you don't have to worry about programs getting stuck and blocking/crashing the interpreter which is running them (in this case, the main Bitcoin software).
Not having to deal with the halting problem is definitely a plus for a tiny, embedded, purpose-specific language such as the one used for Bitcoin scripts.
It's easier to meter and restrict if it's not Turing complete, remembering that every node in the network needs to execute every script to ensure validity, we want it to be lightweight. It's not like it needs to be any more complex, nobody uses what we have to do anything interesting. Most of the opcodes are completely disabled and there's been no requests for them to be re-enabled.
There's so little use of script that I have manually inspected every single instance of a non-standandard transaction to see what they do. Other than the hash collision competitions and a lot of broken p2pool outputs, nobody to date has done anything even approaching interesting.
In other words, it's not complex because it doesn't need to be.
Question is, at which level would Turing-completeness be useful?
If a single transaction was Turing-complete, then it would have unknowable verification time and could be used as a DoS vector on nodes that would attempt to verify it. With any single transaction having a knowable worst-case verification time, there's no problem of a transaction's validity being unknowable.
But what about transaction chains? The Bitcoin (BTC) network's ScriptVM doesn't have the primitives needed to carry the computation over to the next transaction because there's no way for a locking script to enforce constraints on the outputs (a kind of locking script known as "covenant").
If the ScriptVM would be upgraded with transaction introspection opcodes (which is feasible as a soft-fork), then a transaction chain would become Turing-complete through the use of recursive covenants. There's been some work discussing why this is so: Self-Reproducing Coins as Universal Turing Machine, A. Chepurnoy, Vasily Kharin, D. Meshkov
Note that nodes wouldn't be automatically evolving the multi-TX program. Some blockchain-external agent would have to construct the next transaction that satisfies the covenant and then broadcast it to the network. The program could code-in a reward for this and incentivize anyone to construct and post the next transaction, or external agents could do it for free. The program would halt when it runs out of money for the fees/incentives, but then again, other external agents could give it more money to continue evolving.
Introspection opcodes were proposed (Jan '21) and activated (May '22) on Bitcoin Cash (BCH), a code and blockchain fork of the first Bitcoin blockchain (blocks 0 to 478558 are the same on both blockchains).
Such opcodes were also proposed (Jun '21) as Tapscript opcodes for the Elements experimental Bitcoin sidechain.
Apart from what goatse said, and as your post comments, being not Turing complete means no loops, which could represent a problem with malformed (intentionally or not) scripts.
