An Incomplete Scribe on Bitcoin’s Turing Completeness

Bitcoin Script opcodes are not Turing Complete (TC). Bitcoin is more than just opcodes. Bitcoin is a system designed with constructs like blocks and (more important to the discussion of Turing Completeness) UTXO-based transactions. A script of opcodes alone is not TC, but a system which iterates over a script taking its previous output and using it as input for another script iteration may be Turing complete. The missing piece before we can consider the TC-ness of Bitcoin, is covenants.

A covenant is a script that locks the output (UTXO) from being spent in any way other than defined by the output scriptPubkey (locking-script). A UTXO can be locked to only accepting one or more outputs (UTXO) from a previous transaction as valid input. This way the UTXO from a TX can itself be the only valid input in order to spend that UTXO in a new TX. This covenant on the UTXO means the only way to spend the UTXO is to recursively spend it according to some pre-defined script; this creates a loop (through recursion).

Such a script is possible with OP_PUSH_TX which is not actually an opcode, but a technique using existing opcodes such (colloquially a psuedo-opcode). It’s a technique that involves pushing the the entire TX that is meant to spend a UTXO on the stack in the unlocking script (scriptSig) for that UTXO. This allows the locking-script from the UTXO (scriptPubkey) to evaluate the entire TX using opcodes that can deterministically check the "transaction-template" of the TX for validity. Specifically, it allows the locking-script to ensure that an output is present in the TX and that its "script-template" is a valid to the program.

With the self-referential nature of OP_PUSH_TX, a locking-script can constrain that the output is an iteration of a loop. This is exactly like a recursive function in functional programing languages. Each time one of these covenanted outputs is spent, it can simulate a function calling itself.

EVM byte-code (opcodes) requires that a runtime (virtual machine) executes the byte-code correctly. Because loops are in the opcodes, a single transaction my never halt. For UTXO-based systems, the loop is not within the opcodes, it’s simulated by multiple TXs which may never halt. In fact, if UTXOs ever were to halt, that would mean that they’re un-spendable; hopefully no value is left in those UTXOs. These UTXOs generally contain an OP_RETURN with no value, and instead some artifact of the program (data).

In EVM-based systems, gas-limits are defined to make sure a program that has not yet halted is valid at some particular point of execution. This is an insurance policy for the miner who validates that the program is not expending resources without being paid. In UTXO-based systems, a partially complete program is valid because it’s a set of TXs linked by a UTXO chain. The miner gets paid no matter what because all the TXs are valid with fees. Partially complete states can always be continued so long as more funds are vested to pay for the fees for validation.

Hopefully, this is a straight-forward explanation to how one could run programs on Bitcoin. So long as there is a way to covenant some UTXOs to be spent specifically such that is executes a set of rules determined by a program/algorithm, then Bitcoin is Turing Complete by this definition:

"To show that something is Turing-complete, it is enough to show that it can be used to simulate some Turing-complete system. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete."

The rule-set defined by opcodes and the ability to covenant the outcome of a script such that it governs that the same script is propagated in UTXOs, then we have an effective way to do recursion and therefore loops with rules. I don't have a proof whether the rules provided by the opcodes are enough to do any algorithm, but the set of what operations are required to simulate any generic computation is small, and I can say with conjecture that the set of opcodes encompasses that.