How Bitcoin and Ethereum solved the Halting Problem differently

Why is this important?

  • Ethereum Network natively supports complex arbitrary bytecode. Bitcoin Network does not. Complex arbitrary turing-complete bytecode language is necessary for ‘colored coins’ (tokens) and for trustless DeFi because it allows for smart contracts which can perform multi-asset atomic swaps (DEX swaps) in which Asset A is sent from Alice to Bob and Asset B is sent from Bob to Alice in one transaction and which can also perform programmatic escrow of liquidity in trustless ‘vaults’.
  • The Bitcoin Network does not support complex arbitrary bytecode and does not have many custom assembly instructions, so ‘colored coins’ (tokens) and DEX swaps are not possible on the network. All transactions can only be uni-directional, requiring a trusted third party custodian for all transactions. Either you trust Bob to uphold their end of the ‘deal’ (whatever it is) when you pay them, or you use a centralized trusted third party to help conduct the deal.

How did each network solve the Halting Problem?

A blockchain that processes transactions from users is a computing machine. Consider the following:

  • Bitcoin Network solved this problem by reducing the potential complexity of assembly instructions so that it is impossible for a transaction to halt. By disallowing loops and by limiting the bytecode instructions such that the execution machine is not ‘Turing complete’, the halting problem is avoided. However, this deeply limits the capabilities of the network. With this paradigm, transactions can never roll back atomically because they never need to rollback as there can never be a halt.
  • Ethereum Network solved this problem in a way that maintains the complexity of assembly instructions such that the EVM is fully ‘Turing complete’ and able to process arbitrary executable bytecode uploaded by users (smart contracts.) Ethereum solves the Halting Problem by requiring that each executed instruction requires payment of ‘gas’ and by running out of gas or by erroring, the transaction atomically rolls back to the beginning and rewinds state.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store