<p>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. </p>

<p>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 <a href="https://bitcointalk.org/index.php?topic=293382.0">hash collision competitions</a> and a lot of broken p2pool outputs, nobody to date has done anything even approaching interesting. </p>

<p>In other words, it's not complex because it doesn't need to be.</p>

CC BY-SA 3.0
2014-05-18T13:22:56.300Z
2014-05-18T13:22:56.300Z
user13413
<p>Question is, at which level would Turing-completeness be useful?</p>
<p>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.</p>
<p>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 &quot;covenant&quot;).</p>
<p>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: <a href="https://www.semanticscholar.org/paper/Self-Reproducing-Coins-as-Universal-Turing-Machine-Chepurnoy-Kharin/05c6514c671d380cb2aa02ffa504bb4faca7b92c" rel="nofollow noreferrer">Self-Reproducing Coins as Universal Turing Machine, A. Chepurnoy, Vasily Kharin, D. Meshkov</a></p>
<p>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.</p>
<p>Introspection opcodes were <a href="https://gitlab.com/GeneralProtocols/research/chips/-/blob/master/CHIP-2021-02-Add-Native-Introspection-Opcodes.md" rel="nofollow noreferrer">proposed (Jan '21)</a> and <a href="https://documentation.cash/protocol/forks/hf-20220515.html" rel="nofollow noreferrer">activated (May '22)</a> on Bitcoin Cash (BCH), a code and blockchain fork of the first Bitcoin blockchain (blocks 0 to 478558 are the same on both blockchains).</p>
<p>Such opcodes were also <a href="https://github.com/ElementsProject/elements/blob/master/doc/tapscript_opcodes.md" rel="nofollow noreferrer">proposed (Jun '21)</a> as Tapscript opcodes for the Elements experimental Bitcoin sidechain.</p>

CC BY-SA 4.0
2023-09-25T14:07:51.363Z
2023-09-25T16:20:45.547Z
2023-09-25T16:20:45.547Z
bca-0353f40e
<p>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.</p>

CC BY-SA 3.0
2014-05-18T19:22:23.813Z
2014-05-18T19:22:23.813Z
perencia
<p>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 <em>when</em> and <em>how</em> 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).</p>

<p>Not having to deal with the <a href="http://en.wikipedia.org/wiki/Halting_problem">halting problem</a> is definitely a plus for a tiny, embedded, purpose-specific language such as the one used for Bitcoin scripts.</p>

CC BY-SA 3.0
2014-05-18T19:34:50.110Z
2014-05-18T19:34:50.110Z
Massimo
<p>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?</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Retrieved from: <a href="https://en.bitcoin.it/wiki/Script">https://en.bitcoin.it/wiki/Script</a>.</p>

<script><turing-completeness>
The Bitcoin scripting system is purposefully not Turing-complete - why?
Giulio Prisco
# The Bitcoin scripting system is purposefully not Turing-complete - why?

(Asked by: username_0 on 2014-05-18)

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>.

**Tags:** script, turing-completeness


---

## 4 answers

### Answer by username_4 on 2014-05-18. Score: 15 | Accepted answer

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](http://en.wikipedia.org/wiki/Halting_problem) is definitely a plus for a tiny, embedded, purpose-specific language such as the one used for Bitcoin scripts.


---

### Answer by username_1 on 2014-05-18. Score: 6

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](https://bitcointalk.org/index.php?topic=293382.0) 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.


---

### Answer by username_2 on 2023-09-25. Score: 2

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](https://www.semanticscholar.org/paper/Self-Reproducing-Coins-as-Universal-Turing-Machine-Chepurnoy-Kharin/05c6514c671d380cb2aa02ffa504bb4faca7b92c)

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)](https://gitlab.com/GeneralProtocols/research/chips/-/blob/master/CHIP-2021-02-Add-Native-Introspection-Opcodes.md) and [activated (May '22)](https://documentation.cash/protocol/forks/hf-20220515.html) 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)](https://github.com/ElementsProject/elements/blob/master/doc/tapscript_opcodes.md) as Tapscript opcodes for the Elements experimental Bitcoin sidechain.


---

### Answer by username_3 on 2014-05-18. Score: 1

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.


---

