Title: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: Felicity_Tide on July 05, 2024, 09:39:18 PM 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 Quote from: lightning.network link=https://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. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: d5000 on July 05, 2024, 10:18:31 PM 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: 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 (https://protos.com/turing-complete-smart-contracts-arrive-on-bitcoin/). [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. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: larry_vw_1955 on July 06, 2024, 12:22:05 AM 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. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: ABCbits on July 06, 2024, 08:47:50 AM 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 (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. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: DaveF on July 06, 2024, 12:46:17 PM 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 Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: vjudeu on July 06, 2024, 12:52:27 PM Quote Does Bitcoin still operates on the Turing-Incomplete system? Yes.Quote And why? Because of the halting problem (https://en.wikipedia.org/wiki/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.Quote 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 (https://en.wikipedia.org/wiki/Brainfuck) implementation is Turing complete.Quote and what are simple examples of things that are Turing complete? If you want a Bitcoin-related example, then imagine that the current Script (https://en.bitcoin.it/Script) would have not only OP_IF, but also OP_WHILE. That would be sufficient to make it Turing-complete.Quote 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.Quote 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. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: Felicity_Tide on July 06, 2024, 12:56:18 PM 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... Quote In Python-like pseudocode this could be something like this: Code: for tx in incoming_transactions: 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. Quote This is very simplified because in Bitcoin a transaction can have various senders, but I hope you get what I mean. Yes, I do. Quote 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 (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?. Quote 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?. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: BlackHatCoiner on July 06, 2024, 01:17:04 PM 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 The good question is how could this be implemented in Script, if OP_WHILE existed? Bounty 50 merits for whoever answers this correctly. ;D Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: Felicity_Tide on July 06, 2024, 02:20:06 PM 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 The good question is how could this be implemented in Script, if OP_WHILE existed? Bounty 50 merits for whoever answers this correctly. ;D Code: OP_PUSHNUM 0 // same as (int i=0;), which would initialize the variable I=0 Not sure if I relate it well with the C code. I doubt if this would work. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: vjudeu on July 06, 2024, 02:28:25 PM Quote 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 Quote 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: +--------------------------------+ Code: +--------------------------------+ Then, Alice can grab hex bytes of this transaction, and add her input: Code: +--------------------------------+ Quote 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 Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: BlackHatCoiner on July 06, 2024, 03:52:20 PM [...] It's a good attempt, but here's a few questions:
[...] 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). Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: vjudeu on July 06, 2024, 04:05:08 PM Quote 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: Quote 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 Code: signrawtransactionwithwallet "02000000014670c93e91f469b9992578d9c048627ffd4ea5bcc4a7269386f5d632604fb7450000000000fdffffff0100c2eb0b00000000160014c41c546a84eab1860ef7a81e32050d2cf2db31d300000000" "[]" "ALL|ANYONECANPAY" Code: 7a6aa334a174d84697395b348cca15e5263b58c0e1b44381e3c77ee28326c699:0 2.00000000 Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: Felicity_Tide on July 06, 2024, 07:11:28 PM 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. Quote
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. Title: Re: Does Bitcoin still operates on the Turing-Incomplete system? And why? Post by: d5000 on July 07, 2024, 03:03:49 AM 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 (https://rgb.tech) 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. |