Re:Critical Update on DAO Vulnerability
by LoSboccacc on Friday June 17, 2016 @08:38AM
(#11922248)
that's the gist of the problem
Turing machine, meet halting problem.
The halting problem is easy to solve for Ethereum programs by design. Programs are made of instructions, each instruction requires fuel to run, and fuel is limited, so every program must halt eventually.
Re:Critical Update on DAO Vulnerability
by roywiggins on Friday June 17, 2016 @06:08PM
(#11925859)
I'm not familiar with Ethereum programs, but it seems to me that it's not possible to answer the practically-identical question, "How much gas does this program need to start with to guarantee it will either get into a loop or halt of its own accord before it runs out of gas?"
Or, to put it another way, it sounds like the language is Turing complete in roughly the same way C is Turing complete even though every C program ever instantiated is actually a linear bounded automaton because there's no such thing as an infinite tape.
Like, I can announce that my C-like language will always halt after a trillion-trillion operations and therefore the halting problem is "solved" for it, but for all other purposes it's almost exactly as difficult to reason about as a Turing machine.
It most likely is not, looking at the recent post on contract security, most if not all examples ever posted as best practice are flawed and can be exploited:
https://blog.ethereum.org/2016/06/10/smart-contract-security... (currently down, cached version https://webcache.googleusercontent.com/search?q=cache:https:...)