Does Bitcoin still operates on the Turing-Incomplete system? And why?

[Felicity_Tide]

So, I came across the term "Turing completeness" few days back. The name Alan Turing flashed across my mind, as I once watched a movie about him titled "The Imitation Game" (if I am not wrong). Fortunately for me, Turing Complete/Incomplete concepts are related to many things, including Bitcoin and Ethereum.

I have been wrapped/trapped in the Turing/non-Turing concepts for a while now, which has made me almost skip it and find something else to read about. But as long as Bitcoin is involved, the urge to learn about its Blockchain part, keeps dragging me back. So I need to learn how it relates to Bitcoin.

From the major and simple definitions I could gather, they defined Turing complete as any system or the capacity for a computer to perform complex computations when provided with the necessary resources such as memory and time. The definition was quite easy to understand, as I could easily picture something like smart contract from this definition. Next was for me to identify what it has to do with Bitcoin.

Most of the articles online classified Bitcoin as Turing incomplete, while Ethereum as Turing complete, which I can't understand or comprehend their reasons for, which is because Ethereum can execute smart contracts. Ideally, we all know that Ethereum was primarily designed not just to conduct its regular token transactions but also to build DApps and implement smart contracts on it. This point really doesn't justify anything much, because Bitcoin is never an exception.

Though, I still find the entire Turing complete/incomplete contradicting, what actually prompted the question above is that: Bitcoin was primarily designed as a p2p electronic cash system, but not until few years back when we began to see other implementations on Bitcoin like the LN. The lightening Network, lightening for short, according to lightning.network

is a decentralized network using smart contract functionality in the blockchain to enable instant payments across a network of participants.

which means there are smart contract-like concepts on the Bitcoin blockchain as well. Then why is it still considered Turing incomplete, I asked myself. I guess I am getting the entire concept wrong, starting from the Turing complete system.

My Questions:
1. What is actually a Turing complete system, and what are simple examples of things that are Turing complete?.
2. Why is Bitcoin classified a Turing Incomplete system, but Ethereum a Turing complete?.
3. Are there advantage and disadvantage for any system that is either Turing complete or incomplete?.
4. Does Bitcoin still operates on the Turing-Incomplete system?.
5. Is solidity programming strictly for implementing Smart contracts on the Ethereum Blockchain only?.

A simple explanation to these questions would be appreciated, as I have already spent about two days trying to understand them without positive results.


I am 100% open to correction as I still see myself as a learner. Pardon any of my error and share your personal opinion. You might want to also DYOR after reading this.

[d5000]

Yes, Bitcoin's Script language is still "Turing incomplete". And it is deliberately so, because of fears that Turing completeness could create attack vectors.

A simple way to understand this is that in a Bitcoin transaction, you can't set conditions which result in a loop. Loops are one of the aspects a Turing-complete programming language usually offers.

For example you can't create the following transaction (stupid example, but that is actually how DEXes work): [1]

"Send 2 Bitcoins to each address which send 1 Bitcoin to my address."

In Python-like pseudocode this could be something like this:

Code:

for tx in incoming_transactions:
  tx_sum = 0
  for output in tx.outputs:
     tx_sum = tx_sum + output.value
  if tx_sum == 1:
     send_btc(2, tx.sender)

This is very simplified because in Bitcoin a transaction can have various senders, but I hope you get what I mean.

In Ethereum such conditions can be created in transactions. This results in "richer" possible smart contracts.

On Bitcoin you can only create a single "row" of conditions and they must be fulfilled in the next step. Loops are not possible. You can use if/else branches though with OP_IF.

It is however possible to create a Turing-complete language for token transactions on the Bitcoin blockchain. However, that would not be the Bitcoin protocol anymore, but a protocol "on top" of it. Counterparty tried this and released an alpha software, but they gave up due to high transaction fees. A newer idea is the BitVM protocol.


[1] Ah, I forgot something: A DEX with Bitcoin is actually possible, but you need various linked transactions (Atomic swaps), or a transaction signed by all participants of the trade. But it works actually a bit different than the Ethereum-like example I gave.

[larry_vw_1955]

3. Are there advantage and disadvantage for any system that is either Turing complete or incomplete?.

compare how with ethereum, a transaction can cost you gas even if it fails. with bitcoin if the transaction doesn't succeed then it doesn't cost you anything. that's the difference.

[ABCbits]

2. Why is Bitcoin classified a Turing Incomplete system, but Ethereum a Turing complete?.

Aside from what what @d5000 said, there are few other limitation of Bitcoin script which described here, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017306.html.

4. Does Bitcoin still operates on the Turing-Incomplete system?.

Yes.

5. Is solidity programming strictly for implementing Smart contracts on the Ethereum Blockchain only?.

No, there are other blockchain / layer which also support Solidity. But it's initially created for Ethereum.

[DaveF]

How about the most basic reason, it does not need it.
BTC is working fine and adding complexity and features like this would not change it's use. Just add more issues.

-Dave

[vjudeu]

Does Bitcoin still operates on the Turing-Incomplete system?

Yes.

And why?

Because of the halting problem. If your program is turing-complete, then you have no way to determine, if it will terminate, and when it will terminate. If you have only "if" statements, then they are executed once or never. If you have "while" loops, then they can never execute, execute once, execute forever (halt), or execute different number of times, depending on the input script.

What is actually a Turing complete system

It is easier to recognize it by examples. If you need a minimal working example, then a full BF-language implementation is Turing complete.

and what are simple examples of things that are Turing complete?

If you want a Bitcoin-related example, then imagine that the current Script would have not only OP_IF, but also OP_WHILE. That would be sufficient to make it Turing-complete.

Why is Bitcoin classified a Turing Incomplete system, but Ethereum a Turing complete?

Because BTC has no loops, while ETH has them. And because of that, there are some kind of limits, to not have some EVM script, which would execute forever, like "OP_TRUE OP_WHILE OP_ENDWHILE <pubkey> OP_CHECKSIG". And also, this is another reason, why users are charged, even if their scripts fail.

Are there advantage and disadvantage for any system that is either Turing complete or incomplete?

The advantage is that if something is Turing-complete, then you don't need any network upgrades. You can do everything inside your scripting language.

The disadvantage is that you cannot quickly check, if some script will terminate in a given time, and how many resources it will consume.

The current solution for Bitcoin is to repeat opcodes as many times, as the maximum number of loop iterations. But because it is expensive, people often execute their contracts on second layers, to avoid those costs, and then they only commit the end result on-chain.

[Felicity_Tide]

For example you can't create the following transaction (stupid example, but that is actually how DEXes work): [1]

"Send 2 Bitcoins to each address which send 1 Bitcoin to my address."

I think the example fits well in this context...

In Python-like pseudocode this could be something like this:

Code:

for tx in incoming_transactions:
  tx_sum = 0
  for output in tx.outputs:
     tx_sum = tx_sum + output.value
  if tx_sum == 1:
     send_btc(2, tx.sender)

took a while to process this. Could a version of this python pseudocode be replicated in C, because I am quite familiar with the basics of C.

This is very simplified because in Bitcoin a transaction can have various senders, but I hope you get what I mean.

Yes, I do.

On Bitcoin you can only create a single "row" of conditions and they must be fulfilled in the next step. Loops are not possible.

Pardon if my questions are quite unrealistic. This single row of conditions, is it also applicable to Lightening Network transactions?, Where two individuals create a channel and begin to make transactions till they are ready to broadcast?.

there are few other limitation of Bitcoin script which described here, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017306.html.

About four were mentioned, but it seems there are more relevant ones. Have they been able to come up with any solutions for the relevant ones?, Because i noticed it was written about since 2019.

Further Addition

The advantage is that if something is Turing-complete, then you don't need any network upgrades. You can do everything inside your scripting language.

The disadvantage is that you cannot quickly check, if some script will terminate in a given time, and how many resources it will consume.

The current solution for Bitcoin is to repeat opcodes as many times, as the maximum number of loop iterations. But because it is expensive, people often execute their contracts on second layers, to avoid those costs, and then they only commit the end result on-chain.

I think this explanation has helped in relieving some doubts as well. In contrast to the last paragraph from your explanation, those it in anyway relates or answer this question I asked d500 previously?.

This single row of conditions, is it also applicable to Lightening Network transactions?, Where two individuals create a channel and begin to make transactions till they are ready to broadcast?.

[BlackHatCoiner]

took a while to process this. Could a version of this python pseudocode be replicated in C, because I am quite familiar with the basics of C.

In C, "Send 2 Bitcoins to each address which send 1 Bitcoin to my address" would look like this:

Code:

struct transaction* IncomingTransactions; // assume there is an array with all incoming transactions
int i=0;   
do{
   int tx_sum = 0;
   for(int j = 0; j < IncomingTransactions[i].total_outputs; j++)
      tx_sum += IncomingTransactions[i].TXO[j].value
   
   if(tx_sum == 1)
      send_btc(2, tx_sender)
   
   i++;
}while(IncomingTransactions[i] != NULL);

The good question is how could this be implemented in Script, if OP_WHILE existed? Bounty 50 merits for whoever answers this correctly.  

[Felicity_Tide]

took a while to process this. Could a version of this python pseudocode be replicated in C, because I am quite familiar with the basics of C.

In C, "Send 2 Bitcoins to each address which send 1 Bitcoin to my address" would look like this:

Code:

struct transaction* IncomingTransactions; // assume there is an array with all incoming transactions
int i=0;   
do{
   int tx_sum = 0;
   for(int j = 0; j < IncomingTransactions[i].total_outputs; j++)
      tx_sum += IncomingTransactions[i].TXO[j].value
   
   if(tx_sum == 1)
      send_btc(2, tx_sender)
   
   i++;
}while(IncomingTransactions[i] != NULL);

The good question is how could this be implemented in Script, if OP_WHILE existed? Bounty 50 merits for whoever answers this correctly.  

Code:

OP_PUSHNUM 0  // same as (int i=0;), which would initialize the variable I=0
   OP_PUSHNUM 0  //  same thing goes for (tx_sum)=0 , which is sum=0
   OP_BEGINFOR // counting the inner loop
   OP_ADD  // (EDITED)
   OP_PUSHNUM 1 // This code should push 1 to the stack
       
      OP_IF // is same as   if(tx_sum == 1)
      OP_PUSHNUM 2 // then the amount of btc will be moved to the stack
      OP_PUSHDATA // the should contain the receiver's address
      OP_SEND_BTC  // sending the 2 btc to the receiver's address
     OP_ENDIF
   OP_ENDLOOP

Not sure if I relate it well with the C code. I doubt if this would work.

[vjudeu]

The good question is how could this be implemented in Script, if OP_WHILE existed?

If you have BF language, mentioned above, then it has simple while loops. The difference between OP_IF and OP_WHILE is simple: OP_IF is executed once, and then forgotten. OP_WHILE is executed constantly, as long as the top element of the stack is true.

Which means, that you can have a valid Script: <condition> OP_IF <code> OP_ENDIF
And a valid loop is quite similar: <condition> OP_WHILE <code> OP_ENDWHILE

Send 2 Bitcoins to each address which send 1 Bitcoin to my address

This can be splitted into:

1. You send me 1 BTC.
2. I send you back 2 BTC.

Let's see, how it would look like, purely transaction-wise, without any Script:

Code:

+--------------------------------+
| Alice 1.01 BTC -> Bob 1.00 BTC |
+--------------------------------+

+--------------------------------+
| Bob 1.00 BTC -> Alice 2.00 BTC |
| Bob 1.01 BTC                   |
+--------------------------------+

In practice, it can be done today, if you know, how to use something more than SIGHASH_ALL. No Turing-completeness is needed. First, let's assume that Bob has some funds, which he wants to send to Alice. He can craft this transaction, signed with SIGHASH_ANYONECANPAY:

Code:

+--------------------------------+
| Bob 1.00 BTC -> Alice 2.00 BTC |
+--------------------------------+

Obviously, it has negative fee, equal to -1.00 BTC. It simply creates coins out of thin air. However, it is not fully signed. It has ANYONECANPAY flag, which means, that "anyone can pay", meaning that "anyone" can "add more coins as inputs". So, Bob provides his signature, and sends this transaction into Alice (without using P2P Bitcoin network, because it would reject this transaction, because of "negative fee").

Then, Alice can grab hex bytes of this transaction, and add her input:

Code:

+--------------------------------+
| Bob 1.00 BTC -> Alice 2.00 BTC |
| Any 1.01 BTC                   |
+--------------------------------+

As you can notice, it can be anything: sent into Bob, sent into Alice, just anything at all. It does not matter, because Alice will not receive her 2 BTC, if she will not attach her coins. In practice, the most convenient way is to attach original Alice's coins there, without sending them to Bob at all. In this way, everything can be compressed into a single transaction, and serve the same purpose ("sign my transaction, and I will give you my coins"). Because what Bob can achieve in this contract, is to have his own coins signed with Alice's signature (yes, she can also use different sighashes than SIGHASH_ALL, but it would be unsafe for her).

Bounty 50 merits for whoever answers this correctly.

I have enough merits, I am more interested in doing that in practice, for example in testnet3 or testnet4. So, do you want to receive some test coins for sending some? As you can see above, I need Alice's address as a destination.

Edit: I am ready, I got some coins from Garlo Nicon for this experiment:

https://mempool.space/testnet4/tx/45b74f6032d6f5869326a7c4bca54efd7f6248c0d9782599b969f4913ec97046#vout=0
https://mempool.space/testnet/tx/9f523a213550f813e049c0ef9489e2739eada990e2e37e17caeb1ae4527390cd#vout=0

[BlackHatCoiner]

[...]

It's a good attempt, but here's a few questions:

• Would this be an unlocking or locking script? The sender would somehow need to know that he'll get the 2 BTC beforehand. This implies, to me, that the sender will lock his bitcoin to this condition.
• What does OP_ADD add? You say that you add transactions, but OP_ADD adds the top two numbers in the stack.

[...]

That's indeed a smart solution to our problem, but I was wondering if it can be implemented non-interactively, meaning, without having to interact with Alice. Could this work by playing with Script? For example, Alice constructs an address which, if ever receives 1 BTC, an unlocking script can be constructed by the sender, so that he can spend that bitcoin, plus another (from another UTXO).

[vjudeu]

but I was wondering if it can be implemented non-interactively

With OP_CAT? Sure. Then, you require a valid signature, and you explore the currently executed transaction to check, if Alice's address is on both sides, with proper amounts (which means, that you just OP_CAT some pre-defined bytes, with some user input from the stack, you hash it, and then you use OP_CAT to combine it with OP_CHECKSIG, to act like OP_CHECKSIGFROMSTACK).

Edit:

For example, Alice constructs an address which, if ever receives 1 BTC, an unlocking script can be constructed by the sender

Sure, here you are:

Code:

45b74f6032d6f5869326a7c4bca54efd7f6248c0d9782599b969f4913ec97046:0   1.00000000 tBTC
9f523a213550f813e049c0ef9489e2739eada990e2e37e17caeb1ae4527390cd:0   1.00000000 tBTC

createrawtransaction '[{"txid":"45b74f6032d6f5869326a7c4bca54efd7f6248c0d9782599b969f4913ec97046","vout":0}]' '[{"tb1qcsw9g65ya2ccvrhh4q0rypgd9nedkvwn7ss2y5":2.00000000}]' 0 true
02000000014670c93e91f469b9992578d9c048627ffd4ea5bcc4a7269386f5d632604fb7450000000000fdffffff0100c2eb0b00000000160014c41c546a84eab1860ef7a81e32050d2cf2db31d300000000

createrawtransaction '[{"txid":"9f523a213550f813e049c0ef9489e2739eada990e2e37e17caeb1ae4527390cd","vout":0}]' '[{"tb1qcsw9g65ya2ccvrhh4q0rypgd9nedkvwn7ss2y5":2.00000000}]' 0 true
0200000001cd907352e41aebca177ee3e290a9ad9e73e28994efc049e013f85035213a529f0000000000fdffffff0100c2eb0b00000000160014c41c546a84eab1860ef7a81e32050d2cf2db31d300000000

This means "if I receive 1 BTC here". Now, we can sign it properly:

Code:

signrawtransactionwithwallet "02000000014670c93e91f469b9992578d9c048627ffd4ea5bcc4a7269386f5d632604fb7450000000000fdffffff0100c2eb0b00000000160014c41c546a84eab1860ef7a81e32050d2cf2db31d300000000" "[]" "ALL|ANYONECANPAY"
{
  "hex": "020000000001014670c93e91f469b9992578d9c048627ffd4ea5bcc4a7269386f5d632604fb7450000000000fdffffff0100c2eb0b00000000160014c41c546a84eab1860ef7a81e32050d2cf2db31d30247304402201f564ec360a041990920df6fbc52424c7c9f2f77f3ea6b416d09708e095e6d7502206769c8969603da8ce6ee33df5e74a6a20a8ded15bf6333798da3c3f7b500236f8121033f460061d51bafcd3157698cd2db74c511d75cd824a77ee1b525712bfdf9857c00000000",
  "complete": true
}

signrawtransactionwithwallet "0200000001cd907352e41aebca177ee3e290a9ad9e73e28994efc049e013f85035213a529f0000000000fdffffff0100c2eb0b00000000160014c41c546a84eab1860ef7a81e32050d2cf2db31d300000000" "[]" "ALL|ANYONECANPAY"
{
  "hex": "02000000000101cd907352e41aebca177ee3e290a9ad9e73e28994efc049e013f85035213a529f0000000000fdffffff0100c2eb0b00000000160014c41c546a84eab1860ef7a81e32050d2cf2db31d30247304402203b216ca8e210cebf50269f3e388cfa59fa02aff45ed20486f4424876d20310cc02201c28725190720981c4a3649feeea39423568c8f097252824d7a97224815a6c0f8121033f460061d51bafcd3157698cd2db74c511d75cd824a77ee1b525712bfdf9857c00000000",
  "complete": true
}

And then, my job here is almost done. Almost, because now I am 100% sure, that I can receive 1 tBTC in a decentralized way, just from anyone. And then, if I wouldn't care, I could just release my coins, without any conditions:

Code:

7a6aa334a174d84697395b348cca15e5263b58c0e1b44381e3c77ee28326c699:0   2.00000000
947a146aaa2b84b64943e8e31c5464eb194abf5a3ecf2dd6788889366e4b875b:0   2.00000000

createrawtransaction '[{"txid":"7a6aa334a174d84697395b348cca15e5263b58c0e1b44381e3c77ee28326c699","vout":0}]' '[{"data":"00"}]' 0 true
020000000199c62683e27ec7e38143b4e1c0583b26e515ca8c345b399746d874a134a36a7a0000000000fdffffff010000000000000000036a010000000000

createrawtransaction '[{"txid":"947a146aaa2b84b64943e8e31c5464eb194abf5a3ecf2dd6788889366e4b875b","vout":0}]' '[{"data":"00"}]' 0 true
02000000015b874b6e36898878d62dcf3e5abf4a19eb64541ce3e84349b6842baa6a147a940000000000fdffffff010000000000000000036a010000000000

signrawtransactionwithwallet "020000000199c62683e27ec7e38143b4e1c0583b26e515ca8c345b399746d874a134a36a7a0000000000fdffffff010000000000000000036a010000000000" "[]" "NONE|ANYONECANPAY"
{
  "hex": "020000000199c62683e27ec7e38143b4e1c0583b26e515ca8c345b399746d874a134a36a7a0000000000fdffffff010000000000000000036a010000000000",
  "complete": false,
  "errors": [
    {
      "txid": "7a6aa334a174d84697395b348cca15e5263b58c0e1b44381e3c77ee28326c699",
      "vout": 0,
      "witness": [
      ],
      "scriptSig": "",
      "sequence": 4294967293,
      "error": "Input not found or already spent"
    }
  ]
}

signrawtransactionwithwallet "02000000015b874b6e36898878d62dcf3e5abf4a19eb64541ce3e84349b6842baa6a147a940000000000fdffffff010000000000000000036a010000000000" "[]" "NONE|ANYONECANPAY"
{
  "hex": "02000000015b874b6e36898878d62dcf3e5abf4a19eb64541ce3e84349b6842baa6a147a940000000000fdffffff010000000000000000036a010000000000",
  "complete": false,
  "errors": [
    {
      "txid": "947a146aaa2b84b64943e8e31c5464eb194abf5a3ecf2dd6788889366e4b875b",
      "vout": 0,
      "witness": [
      ],
      "scriptSig": "",
      "sequence": 4294967293,
      "error": "Input not found or already spent"
    }
  ]
}

Well, almost there. Why almost? Because without SIGHASH_ANYPREVOUT (or rather: SIGHASH_PREVOUT_REPEAT, which would consider previously used sighashes), the user cannot really touch our initial transaction, because it will change transaction ID, and our SIGHASH_NONE | SIGHASH_ANYONECANPAY signature would be suddenly invalid. So close! But with SIGHASH_ANYPREVOUT, it can be signed, as shown above, and then no interaction from Alice is needed.

[Felicity_Tide]

Would this be an unlocking or locking script? The sender would somehow need to know that he'll get the 2 BTC beforehand. This implies, to me, that the sender will lock his bitcoin to this condition.

This should work as a locking script, since there is a condition that has been set or must be met before the sender gets the 2 Btc.

• What does OP_ADD add? You say that you add transactions, but OP_ADD adds the top two numbers in the stack.

You are right.
I just couldn't express the explanation using comment, but here is another trial:

From the code I could come up with, The op_add is basically adding the OP_PUSHNUM 1 with value 1 to the stack, and remember that the stack already contains a value 0 from OP_PUSHNUM 0(tx_sum) as specified in line 2, leading to the addition of 0+1, since they are the top two numbers available in the stack. This would then give rise to a new sum( tx_sum==1), which I think matches the condition, before the next OP_PUSHNUM 2 is exceuted.

Kind of contradicting, but this is just what I could come up with. Am looking forward to all corrections.

[d5000]

Pardon if my questions are quite unrealistic. This single row of conditions, is it also applicable to Lightening Network transactions?, Where two individuals create a channel and begin to make transactions till they are ready to broadcast?.

At least the individual transactions on "pure" Lightning network do use Bitcoin Script, even if they are exchanged offchain between the participants. So they can also contain no loops but only a "row" of conditions.

You wrote in the OP that you read that Lightning uses "smart contracts", and yes, that is true: the HTLCs are smart contracts. But these contracts do not need a Turing-complete environment, because their conditions are executed one after another, with if-else branching. In Lightning's HTLCs, for example it is typical to require either a secret (hashlock) or a waiting time (timelock), but once one of both is provided the coins can be transferred. It is still a "row" even if it has if-else branches.

You can however build a protocol on top of Bitcoin and Lightning to allow loops of conditions. AFAIK that is what RGB is attempting. But also AFAIK (I'm not 100% sure but only 90% ) this protocol could never affect Bitcoin UTXOs, i.e. "Bitcoin transactions", but only token transactions based on this protocol "on top of Bitcoin". You could for example imagine such a system allowing loops for Counterparty transactions or Runes.

On sidechains, loops are possible if the sidechain protocol provides a language/VM to execute contracts with loops/recursion. That's actually what Rootstock's goal is, although their system is still quite centralized.

[ercewubam]

@vjudeu: Contract executed: https://mempool.space/testnet/tx/70f8a2d9e01f8603cc0301fe5b3b809c5a9acfc975a5f122393b1c900b977cba

As everyone can see, the recipient can simply publish some partially-signed transaction, and then the sender can do the rest, without any interaction.
Challenge for readers: repeat the same thing on testnet4. It is easier to get them, because each block will give you at least 50 new coins.