What does the halting problem have to do with Ethereum?

In trying to understand what Ethereum was, I was "thrown for a loop" on day one a bit. That was by the introduction regarding the halting problem--which is repeated currently on the Wikipedia entry:
Ethereum is a decentralized publishing platform featuring stateful user-created digital contracts and a Turing-complete contract programming language. Ethereum uses its underlying network unit, ether, as payment to execute Ethereum contracts as a workaround to the Halting Problem.
I didn't understand this statement then, before knowing what Ethereum was. Now after reading and being fairly confident I "get it" (arbitrary code and state storage engine, leveraging first-to-file concepts of bitcoin, decentralized ledger verification but *not* decentralized authority)...I still don't know how it is meaningful to invoke the halting problem to explain it.

Consider: if I ask Amazon Elastic Computing cloud why they charge me per processor cycle, or why I have to pay more for a larger disk, they don't snap back with: "because of the halting problem". Computation and storage requires resources: Turing-complete or not. If you are asking a network to do computation or storage on your behalf, it doesn't matter whether you can analyze a program to determine if it halts. The network must be willing to bear the burden of running your code and saving your data under some incentive.

So does anyone have a concrete answer as to why the halting problem is being invoked so often? How is the protocol in any way affected by its inability to determine if the contracts it is being asked to execute terminate or not? Why would the collective network agree to execute a long-running (but guaranteed to terminate...someday...) contract without cost?

Comments

  • avsaavsa Member Posts: 68 ✭✭
    Honestly I'd say it's two things:

    First, ethereum is a complex system and the more you explain it, the better you get at it, specially at ignoring things that don't matter at first. So that explains why there would be a more complicated answer where a simple "since computation is a finite resource provided voluntarily, ether is used as a payment".

    Secondly, the people who write ethereum descriptions are mostly cryptographic and CS nerds who are much more interested in talking about the Byzantine generals or the Halting problem and less about economic incentives.
  • MarioFortierMarioFortier Boston, MAMember Posts: 30
    edited September 2014

    The network must be willing to bear the burden of running your code and saving your data under some incentive.

    As long the burden does not affect the usefulness and security of the network.
    So does anyone have a concrete answer as to why the halting problem is being invoked so often?
    Two examples of incentive for talking about the halting problem:
    (1) It is economically important for the miner to have capability to exit from a malicious or buggy transaction that takes an abnormal long time to complete. A transaction taking "forever" would be a net loss to the miners.

    (2) It is functionally important for most users to get their transactions processed and verified on a timely manner. Getting all nodes busy a few hours on running a single transaction would bring the network to a dead stop.

    The halting problem is to never be sure if a transaction will complete without actually running it, so it is very important for the protocol to provide runtime workarounds. Since a few key features of Ethereum is to specifically counter the halting problem... I am not surprise to see it mention often.
    How is the protocol in any way affected by its inability to determine if the contracts it is being asked to execute terminate or not?
    The protocol includes a limit beyond which the miner should abandon the execution.

    The protocol also reward the miner even if the execution of the transaction never completes (avoid no-cost attacks).

    The protocol makes all miners terminate at the same limit (network consensus to give up).

    The protocol also allows for miners to independently decide to give up (without being paid) on any transaction.

    I probably miss a few other ways the Ethereum protocol helps against the halting problem...

    \Mario
    Post edited by MarioFortier on
  • HostileForkHostileFork Member Posts: 6
    edited September 2014
    @MarioFortier‌
    The halting problem is to never be sure if a transaction will complete without actually running it, so it is very important for the protocol to provide runtime workarounds.
    I'm afraid with all the examples you give, I still don't see the difference between a long-running program that is guaranteed to halt...and one that makes no guarantee.

    The network would need a consensus on a limit of how long to run a transaction either way.

    Only if computers were infinitely fast could someone argue that it mattered, because programs would have two durations to run: forever or instantly. You might make a case that if you were modeling network nodes as infinitely fast computers then it would force one's hand to introduce a scarce resource. That's the only thing I can think of.
  • PeterBBPeterBB Member Posts: 4
    You're right that, in practice, "arbitrarily long" is just as bad as "non-halting". But the halting problem works as a nice, clear justification for gas costs, because it means that it's impossible even in theory to have a Turing-complete cryptocurrency without some equivalent measure.
  • StephanTualStephanTual London, EnglandMember, Moderator Posts: 1,282 mod


    I'm afraid with all the examples you give, I still don't see the difference between a long-running program that is guaranteed to halt...and one that makes no guarantee.
    The network would need a consensus on a limit of how long to run a transaction either way.

    Because it *cost* to run. Allow me to simplify:
    - Computers can only do so many operations per block
    - The amount of gas that can be used is limited per block (there's a gas per block limit)
    - The gas price is variable

    Therefore, if someone really rich in ether, they could send transactions to contracts that run very time consuming operations, maybe running serpent operated ECRECOVER operations for example. They would need to price the gas through the roof so that all miners decide to prioritise these transactions before all others. Writing to the ethereum network would become hard if not impossible for everyone but that person until... that person runs out of money.

    Before you say 'oh but some people are very rich and evil', you need to understand that:
    1) Reaching the gas limit will cost an absolute fortune per block, every 12.7s. I don't care if you're Bill Gates and secretly bought all the Ether in the world, you're going to run out, and fast. There's only so much ether out there.
    2) All you'll have achieved is make the world's miners very happy for a few minutes.

    And that's how the halting problem is solved.
Sign In or Register to comment.