Turing complete language vs non-Turing complete (Ethereum vs Bitcoin)

[lebing]

The concept of a Turning complete scripting language has come up as essentially the defining feature of this new coin, ethereum. If we assume Satoshi purposefully left out this feature set (as the developers of ethereum maintain), was that intentional because having this functionality is in itself to risky to the infrastructure? What does the community think regarding this distinction & what does the risk/ benefit look like?

[theymos]

Satoshi probably left it out because making a Turing-complete transaction scripting language safe is more difficult. You have to prevent scripts from running endlessly while also allowing them to run long enough to be useful, and you can't let them access too much external data or they might become invalid after being valid for a while and really screw things up. A Turing-complete transaction scripting language would be really cool, though. If done well, it could be used to add all sorts of new features (even new crypto) in a backward-compatible way.

I don't know much at all about Ethereum, but it looks like their scripts can access info about blocks, which seems dangerous. If this was possible in Bitcoin, then a reorg could cause many fully-confirmed transactions to all of a sudden become invalid by accident, without even any attacker. This is very undesirable. Maybe Ethereum does something to fix this -- I don't know.

[bitfreak!]

Satoshi only included support for a limited range of transaction types for security reasons but I'm sure he had many ideas about how the scripting system could be used to create a wide range of interesting scripts to serve different purposes. A full turing-complete scripting system seems like a pretty dangerous idea to me but the people working on Ethereum seem to be fairly bright fellows so I'll be interested to see how they tackle this problem. On a some what related note, my mini-blockchain system aims to achieve almost the opposite of what Ethereum is aiming for:

Script is not used within the mini-blockchain scheme. Since the account tree holds the final balance of all non-empty addresses and is not a continuous ledger of transactions like Bitcoin it's not possible to use scripts which must be solved at a later time because transactions in the mini-blockchain are discarded after a relatively small period of time (the length of the mini-blockchain cycle time). However, this is not really as much of a disadvantage as it may seem.

It is still possible to allow more complex types of transactions by defining special account types which support things such as a multi-signature transactions. By not utilizing script we get the advantage of making many aspects of the system exceptionally simpler and at the same we get an increased level of security because every type of possible transaction will be very well defined, eliminating the risk of an unforeseen script causing havoc on the network.

http://bitfreak.info/mbc-wiki/index.php?title=Transaction_Signing

[coinrevo]

yes, there are many reasons this does not exist in bitcoin.

say you want to run arbitrary source code on a p2p node to make possible "smart contracts". how do you know the source is not going to root your operating system? to understand that you have to know how easy and quick introducing backdoors is, in terms of computational complexity. in most cases you have program flow, create some kind of jump, and emulate further normal program flow. usually you have to be quite clever, as Operating System/application developers battle hackers all the time and there is a long list of vulnerabilities. it takes only one bug to introduce a hole. vulnerabilities can be a combination of software and configurations.

writing source code which can predict if source code does what is supposed to do is largely impossible (virus scanners are basically just a list of known vulnerabilities). for smart contracts you need inputs from the outside world, otherwise they are useless. you want inputs like prices, or even a verified date (bitcoin is a timestamp server). if you get data from the outside world that means you can inject any data into nodes you want, and the runner of node has no means to verify whether he is currently executing code which steal his money. remember, in John-Von-Neumann programmable machines code and data exist in the same address space.

as for ethereum. there are some good ideas, but raising millions of dollars very heavily skews the conflict of interest. and I say this in the most friendly way I can. so take all of their claims with a very heavy grain of salt. if you go through the paper you will not find an example of what smart contracts or DAO in this context should even mean. its sad as there is some quite interesting elements. most of it is just nonsense though, if you really think about this should work. most contracts only make sense in terms of possible legal recourse. which is why bitcoin is perfect for uni-directional payments, but useless for everything else.

[MatthewLM]

These contracts from what I tell are verified like the bitcoin scripting language, only with a new language with commands that provide block-chain data, commands that stores information that can be referenced in later contracts and jump commands. They didn't explain how they would limit the execution of contracts. I suppose they will have a limit on the number of steps each contract execution can make.

More interesting than this would be the use of the SNARK programs to replace the scripting system, as previously mentioned elsewhere. That way completely arbitrary programs can be used in transactions.

[maaku]

Replacing the scripting system with SNARK proofs has non-serious problems that remain unsolved. Verifying keys for SNARKs are huge, so it is completely impracticable to compute arbitrary new proof circuits for each output. The most likely alternative is that you compute shared proving and verifying keys for a Turing-complete virtual machine, like tinyram. The problem now is the nature of how the key is generated: a security parameter is chosen which is a sort of master skeleton key - if kept, it could be used to spend anyone's output undetectably. That's no laughing matter. Every known SNARK system with practical requirements has this limitation. In theory you could do some sort of large multi-party compute to create the key in a way where only one participant needs to be honest to ensure destruction of the trapdoor. However besides the practical difficulties of doing this (orders of magnitude greater size problem than anything that's been handled so far), there's the the fact that it only shifts the problem. Practical MPC systems work on the same principle - whoever created the MPC parameters could backdoor that calculation and derive the SNARK security parameter. Try to solve that and its turtles all the way down...

If that weren't bad enough, there's also the issue that while validating a SNARK proof is cheap, creating it is *very* expensive. These sorts of things are typically done on small HPC clusters. It's pretty ludicrous to think of doing it on a smartphone.

Now making a more expressive scripting language is very much possible, but requires being very careful. I'm working on some proposed bitcoin extensions for this.. if anyone is interested in helping out, feel free to PM me.

[behindtext]

Satoshi probably left it out because making a Turing-complete transaction scripting language safe is more difficult. You have to prevent scripts from running endlessly while also allowing them to run long enough to be useful, and you can't let them access too much external data or they might become invalid after being valid for a while and really screw things up. A Turing-complete transaction scripting language would be really cool, though. If done well, it could be used to add all sorts of new features (even new crypto) in a backward-compatible way.

I don't know much at all about Ethereum, but it looks like their scripts can access info about blocks, which seems dangerous. If this was possible in Bitcoin, then a reorg could cause many fully-confirmed transactions to all of a sudden become invalid by accident, without even any attacker. This is very undesirable. Maybe Ethereum does something to fix this -- I don't know.

i definitely agree that the reason this kind of functionality was not added to bitcoin was that it makes shooting oneself in the foot far easier. a related question that could be asked is "why are many of the script opcodes disabled in bitcoind?" and it has the same answer - the functionality that comes with more scripts and more opcodes is risky and creates many more corner cases to code around.

it's obviously possible to do amazing things with more powerful scripting options but i suspect it would not be sufficiently stable and secure as currently proposed in ethereum. bitcoin's success is strongly related to the fact that it is a digital currency system with a few key innovations that added a ton of value, the main innovation being the distributed public ledger. ethereum proposes sweeping changes that are not minor variations and have unknown dynamics in a real-world use case. i do quite like the ideas proposed in the ethereum proposal.

[oakpacific]

I could say I have seen altcoiners trying to change nearly every aspect of Bitcoin, just for the heck of it.

It would have been easy for Satoshi to implement a Turing-complete scripting, he refrains from doing it because Bitcoin is an infrastructure, a security max system, if someone succeeds with remote-exploiting a miner then there is theoretically no limit to the amount of money they can double-spend. Otoh, miners would probably have zero interest in handling complex transactions for you so they will reject most of the opcodes, but it only took one successful exploitation to do irreparrable damage to the network.

[adam3us]

From another thread:

Thanks d'aniel.  My initial feeling is that Turing-completeness is not necessary for bitcoin and would very likely lead to unforeseen problems and instability (mostly related to the halting problem).  Money isn't a computer.

They address halting by fee paying for interpreter cycles.  When the fee runs out the contract is stopped.

But there are obviously interpreter escape dangers, which are harder to contain for a stateful, looping, low level (byte code like) language.  Look at the history of java sandbox escapes.  People say that was mostly due to call outs to complex native library have to look through the (large!) CVE database on JVM to figure out the stats.  Also the pressure may have been lower.  If you get real money under it all kinds of resources and unrevealed 0-days can leak out of the woodwork and create the new target for grey and black hats some of whom are world class at this stuff.  Or even from national security network intrusion insiders with Snowden-level access or the people developing and selling grey market 0-day to the intelligence community etc.  Those people are fallible humans too - they may succum to the financial motive, or the people who developed and sold them the 0-days may find a new monetization model, or second use for them (they cant "forget" them after sale).

There have also been VM escapes from full hw abstraction vms (i mean not just API sandbox light linux-in-linux virtuozzo but actual whole OS in the container).

And finally bitcoin scripting is functional, stateless and non-looping (non TC in fact also) for a reason.  Bitcoin doesnt (and I think its intentional) have even extrospection.  There are grey-goo outcomes if you are not careful with even something as constrained as an extrospection op code to existing language.   There will be whole classes of not yet imagined grey goo opportunities lurking in a full TC language.  You cant easily systematically defend against whole classes of such issues without intentional constrained language.

Here's a thread started by Greg to explore grey-goo outcomes from extended scripting:

https://bitcointalk.org/index.php?topic=278122.0

Greg Maxwell also noted the elevated risk of forks developing.  If there is any deviation in script outcome and being more complex there is more risk there also.  eg tracking how many cycles through a JIT executed/CSE optimized etc version as super-majority of nodes MUST interpret the script to the same byte code instruction, or one version can return true, another false etc.

I discussed these risks with Vitalik and he is a very smart guy, so obviously they'll try to do what they can to contain them, but you know bitcoin is the highest assurance sw dev and QA risk on the planet by orders of magnitude.  So it maybe a time for risk containment rather than risk LoC and API size expansion, I am already worried on bitcoin about base band-processors hacks, 0-day OS and CPU hacks, and thinking a more zero-trust more air-gap model needs to be the objective.

If hypothetically ethereum grew to large adoption (litecoin level say) and then there was enough motivation and something failed hard, there are potential whole system value loss, hard fork and other failure modes.  It seems to have by design, ongoing higher surface area security & value safety risk

Also btw Dan Kaminsky said he spent 4 months trying to hack bitcoin (network stack, overflow on messages, the usual host-security 0-day discovery process) and he failed.  He's one of the best host security guys and the experience impressed him.  Its not a simple thing to make a network stack that bullet proof, most even hard core programmers cant do it.  You probably have to practice 0-day development to some depth to even understand fully the risks and defense landscape.  Bitcoin got there with a really solid start from Satoshi and a bootstrap period where other bugs were fixed before the pressure built up to $10b.

I am not going to comment for now on the funding model  They are somewhere between the others and I am sure Vitalik has his eye on actual innovation as well, because knowing him he lives for tech challenge.

I think anything that needs to be done, can be done in a bitcoin centric backwards compatible evolutionary way using eg 1-way peg and other related features while maintaining value firewalls between long term holders and people using newer features.

But clearly other than the security containment, zero-defect in flight once live, and grey-goo risks, Ethereum can create some fun self-extensibility with a loose analog of like introspection, late binding, eval and dynamically loadable code languages.  We do have to be clear that the cost is the towards opposite end of the spectrum, though lower than activeX and executing native code delivered over the network.  Fun possibilities but a big security job.

Adam

[lebing]

Interesting. It seems that it certainly does not make sense to incorporate it into a protocol when that protocol is designed to be money. However, it seems that it could (alot of answered questions in that could!) make sense if it was designed to compete with the app store.

[coinrevo]

Thanks for the technical comments. Fundraising up to a claimed goal of 36 million USD is not exactly trivial. Conflating money supply issues and in the proof of stake ("IPO") is not helpful in my opinion. so any claims about money supply function is tied to the initial fundraising process. obviously bitcoin completely bootstrapped, so its hard to see for me how this should be an improvement. although I do like the idea that developers get paid for their work. it raises many questions in terms of interaction with the law. private IPO's are not legal.

[Peter Todd]

Also btw Dan Kaminsky said he spent 4 months trying to hack bitcoin (network stack, overflow on messages, the usual host-security 0-day discovery process) and he failed.  He's one of the best host security guys and the experience impressed him.  Its not a simple thing to make a network stack that bullet proof, most even hard core programmers cant do it.

There's nothing impressive about that at all. Those security problems are characteristic of non-bounds-checked languages, and Bitcoin is effectively written in a safe, bounds checked, subset of the C++ language. Meanwhile Dan Kaminsky did miss a whole bunch of dumb and not so dumb DoS attacks, including ones that crash the Bitcoin Core daemon with out-of-memory errors. (e.g. the extra tx data issue where Bitcoin would accept transactions with up to 32MiB of junk data appended to them and keep that all in memory) Quite frankly for him to give such a glowing report of Bitcoin makes me question his competence more than anything else.

[gmaxwell]

Replacing the scripting system with SNARK proofs has non-serious problems that remain unsolved. Verifying keys for SNARKs are huge,

Huh. No, in the (refined) GGPR'12 construction that you're referring to with the other criticisms (e.g. the CRS assumptions) the verifying keys are 2.8KB. This probably compares pretty favorably to program size for any program complicated enough to actually need a turing complete expression. The proving keys are huge, which might be what you were thinking of— but they don't have a major impact on the network.

The verification keys may end up being larger for something without the CRS security assumptions— though as you note its possible to just reuse a single universal circuit for all computations with some efficiency loss.

I think that the more important point in all this is that in a publicly verifiable system like Bitcoin what you want is _not_ execution. What you want is a witness that proves that execution was performed faithfully and what its result was.  There is no need to have an identical computation performed over and over again, it's just waste. In many cases this witness must be at least partially zero knoweldge, in order to prevent miners/other nodes from replaying it and stealing coins.

The simplest way to get a witness for execution is to disclose the code and have everyone perform it again... but it's not the best: It can't be zero knoweldge, it exposes a lot of code that never gets executed, it requires all verifiers to completely reproduce the work— which creates a disincentive against verification which is opposed to the decentralization goals of the system (and if you don't care about trustless decentralization why not just run open transactions?).

SNARKs are a way (well a family of ways) to improve this and in theory they tick a lot of those boxes— e.g. they can achieve zero knoweldge, they can be very small, etc. But SNARKs (esp one particular kind of SNARK) are not the only thing that can be done.  E.g. without invoking moon math we can use the merkelized abstract syntax trees to at least get succinctness and privacy for untaken branches in execution.

In any case, part of the problem with trying to do powerful things in script directly is not that turing completeness itself is hard to make safe— it can be made safe with careful design— but when script evaluation time is non-trivial it will be necessary to build things like JITs to eliminate the 100 fold slowdown from dumbly interpreted evaluation and that will come with a whole host of consistency and safety risks. JITs which are internally indistinguishable from interpreted execution seem to be a pretty much unstudied area.

Keep in mind that execution inside a consensus system multiplies the security considerations of normal sandboxed execution tremendously since absolute consistency becomes a security requirement too, not just memory and control flow integrity.

[coinrevo]

For smart contracts to work one really wants external inputs from the world. For example weather derivatives are an interesting example, say:

sunshine = get_weather('weather.com')
if sunshine:
 pay 1 BTC to xyz
else:
 pay 0.5 BTC to abc

One solution would be to have a trusted source list (weather.com or several sources). The question then is not about node security, but the relationship between a node and some server. One solution might be to sandbox on some external virtual machine image which is specifically used for a transaction.

I'm not sure how much work has been done in terms of virtualization for specific transactions, if at all. one idea is the possible connection of btc to some ("cloud") server. the server takes money for execution and if the balance is zero it destroy itself. on top of a server one can run a pre-build machine image with application software. In the above example you want weather.com to provide a highly stable API, and if it goes down the contract is canceled and you get an insurance payoff. If enough people have economic interest in weather.com to provide a certain interface they can maintain that function with a small amount of btc. This then is not so much a corporation running a service at weather.com but a self maintaining public server. it seems ethereum tries to address this kind of problem, but is missing some primitives. for instance how to run a server without one admin with total control, but rather group control.

[maaku]

There's no way you'd want transaction validation to depend on responses from a specific server. That would destroy distributed consensus. I think that's a terrible example of what to do on the block chain, but if you were to do it you'd have to depend on data committed to the block chain in some way. Otherwise you are destroying the security guarantees of everybody else who uses it.

[pera]

Really short and synthetic text but yet a bit relevant:
http://www.haskell.org/haskellwiki/Safely_running_untrusted_Haskell_code

Anyways, in my opinion the choose of a Forth like language for Bitcoin is one of the wisest decisions made by Satoshi

[coinrevo]

There's no way you'd want transaction validation to depend on responses from a specific server. That would destroy distributed consensus. I think that's a terrible example of what to do on the block chain, but if you were to do it you'd have to depend on data committed to the block chain in some way. Otherwise you are destroying the security guarantees of everybody else who uses it.

What would I want to do with contracts if I can't use inputs? For this reason talk about smart contracts is theory at best, and gibberish at worst. I agree that such a solution is not possible when you talk about traditional servers. for instance just consider the fact that contracts are usually confidential, i.e. not every node should process the information, only the parties involved.

[Mike Hearn]

I think my biggest concern/question mark with Ethereum is that nobody has shown that the limitation on implementing cool stuff inside Bitcoin is script. Script is limited, but even so, most of our ideas never even get close to pushing the boundaries.

The limits on what we can do right now are far more mundane things, like people writing nice GUIs and slick workflows. The underlying cryptography is often very simple. Ethereum isn't focused on solving that.

BTW the latest results on SNARKs have generalised the keys so that you only need one proving key and one verification key (I think) for all programs you might want to ever execute up to a running-time bound. If only proving weren't so expensive, and the math so hard to understand, they'd really be an ideal fit for a next-gen cryptocurrency.

[k99]

I think my biggest concern/question mark with Ethereum is that nobody has shown that the limitation on implementing cool stuff inside Bitcoin is script. Script is limited, but even so, most of our ideas never even get close to pushing the boundaries.

The limits on what we can do right now are far more mundane things, like people writing nice GUIs and slick workflows. The underlying cryptography is often very simple. Ethereum isn't focused on solving that.

BTW the latest results on SNARKs have generalised the keys so that you only need one proving key and one verification key (I think) for all programs you might want to ever execute up to a running-time bound. If only proving weren't so expensive, and the math so hard to understand, they'd really be an ideal fit for a next-gen cryptocurrency.

Vitalik described here (http://bitcoinmagazine.com/9671/ethereum-next-generation-cryptocurrency-decentralized-application-platform) his problems when working in Colored Coins or other Metacoin projects (Mastercoin,...) . It is not only the limitation of scripts but also scalability problems (need full blockchain to operate).

He also introduced other new exciting ideas and concepts (mining algorithms, way how to store the balance, inflation model...) which really drives crypto currencies to a new level.
I really think he deserves a more intense attention and discussion from BTC core devs.
For me it seems by FAR the most interesting project since BTC itself. And Vitalik Buterin has gained his high reputation not by chance. He seems to be one of the brightest minds in the community.

SNARK sounds really promising but due the complexity and open problems not a solution we could expect in the next 2 years I fear.

[coinrevo]

And Vitalik Buterin has gained his high reputation not by chance. He seems to be one of the brightest minds in the community.

what has he actually implemented? the only thing this shows is that is that cryptocurrencies are currently going nowhere, when such drivel can get so much attention. so I ask: where is the source code that does all these magical things? smarts contracts, DAC, ... all of this is simply nonsense the way it is described. and this has little to do with Turing complete languages.