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

[jmw74]

Obviously crypto can't really prove anything about the real world.  That doesn't make "crypto-law" systems useless though.  It just means you have to have some kind of trusted authority to at least certify what happened in the real world, and then the "crypto-law" system can do the rest.

So using your example, if you have a trusted delivery guy Dave who certifies that he received 1 kg cocaine from Alice and delivered it to Bob, then his signature would unlock terms of the contract as-written (payment or whatever).  He could sign that the shipment was damaged in transit and that would unlock some kind of insurance payment.

In scenario B, Alice would ship 1 kg of gold to Bob. She would have to acquire various licenses. Those authorities already exist and are tied to fabric of the global economy. Obviously, in scenario A - shipment of cocaine from Peru to the USA - this is illegal. What gets shipped in the world is determined by nation states and multi-national cooperations. Which natural resources gets shipped where on what conditions is what geopolitics is mostly about. The recent TPP efforts want to establish a kind of cooperate regime, where cooperations can sue governments. This kind of stuff is infinitely complex, and declaring the world your own jurisdiction is not leading to solutions.

In my example, Dave is not UPS, he's a smuggler that works with drug dealers.  You're the one who brought up the cocaine analogy.

If you want to present one that is legal, go ahead, but it would work pretty much the same way.

[bluemeanie1]

a 'computing environment' is not Turing Complete, but computer languages are.

So?  Ethereum is turing complete then.  Running out of ether is part of the environment, not the language.

this poses the first problem of FALSE ADVERTISING.  These aren't turning complete scripts, it's just a bloated up dispatching environment for financial transactions.  I think they're overestimating how 'cool' this is going to be.  It's not going to be fun to make or to use. 

Yes, this is what I think is the real problem, programs are hard to understand and debug.

In law, sure judges are nondeterministic, but they don't do totally insane stuff, like in a parental custody hearing, they don't set their program counter to the wrong number and
Still, I am not sure if this is a fatal flaw, if anything it might limit scripts to what is easily comprehendable by one programmer.  That's still a lot more flexible than bitcoin's scripting system.

I don't really care how they sandbox their environment, in theory it should be a lot simpler than the JVM.  But maybe it is easier to just use the JVM and lock down everything except the few resources ethereum needs access to.  Either way, the sandbox is not going to be what holds them back, I think those already exist and are a proven concept.

The execution environment for this thing would not be very simple.  Another way to achieve this is to make the Bitcoin kernel modular and have the execution happen in a more privileged level, but those modules must be signed by various 'contract definition developers'.  The contracts then are executed by this module and only the variables need to be defined.    I think this may happen with NXT as it's natively Java and lends itself to this idea.  We have a scripting system already in Bitcoin and it's rarely used.  How many different kinds of contracts do they anticipate? 

I think you're attributing some ideas to 'Ethereum' that are really more general concepts that have been floating around for a while.  I don't see many serious dangers at the outset, seems like some overactive imaginations at work.

but as I mentioned, if they want to make this thing and offer it for free to the public then...



-bm

[bluemeanie1]

just reading this paper,



so they have a whole fee system for the various OPCODEs?

you're telling me this is going to be simple?

-bm

[bluemeanie1]

another tidbit, so theyre retailing these 'ether' credits.  Very similar model to Ripple.

[benjyz]

In my example, Dave is not UPS, he's a smuggler that works with drug dealers.  You're the one who brought up the cocaine analogy.

If you want to present one that is legal, go ahead, but it would work pretty much the same way.

If Alice and Bob transact in the year 2014 there is no "crypto-law" that applies. I used the cocaine example to illustrate that you can't violate laws at will. Alice and Bob would most likely go to jail and that would be the end of the story. In the gold example they would be violating all kinds of laws as well. In most modern capitalist societies you can't open any business whatsoever without a license. And cross-borders transactions are much more complicated. Only the most naive anarchists imaginable believe that you can simply ignore the power regime that embodies what we call law.

[behindtext]

It's like removing seat belts from cars and declaring yourself a genius for making us slightly more comfortable. 

lol!

to your point about it being monolithic: after having my devs collectively spend several man years rebuilding bitcoin from scratch (starting in late feb 2013), even having bitcoind as a reference, it's still not finished. there are myriad new features proposed in ETH that all have to be tested before they are released. i suspect that even with a pile of VC money, say >USD 10M, you would be hard-pressed to get all these features coded, tested and added.

while bitcoin is itself relatively complex code-wise, its fundamental insight is rather simple - "use proof of work as both (1) a distributed timestamp and (2) a minting/reward mechanism". if you take 10 such insights, roll them into one, then try to hack out the code, you will soon be in over your head.

[bluemeanie1]

It's like removing seat belts from cars and declaring yourself a genius for making us slightly more comfortable. 

lol!

to your point about it being monolithic: after having my devs collectively spend several man years rebuilding bitcoin from scratch (starting in late feb 2013), even having bitcoind as a reference, it's still not finished. there are myriad new features proposed in ETH that all have to be tested before they are released. i suspect that even with a pile of VC money, say >USD 10M, you would be hard-pressed to get all these features coded, tested and added.

while bitcoin is itself relatively complex code-wise, its fundamental insight is rather simple - "use proof of work as both (1) a distributed timestamp and (2) a minting/reward mechanism". if you take 10 such insights, roll them into one, then try to hack out the code, you will soon be in over your head.

Did you like my monkey picture?  great movie.

sorry not familiar with your project.  Do you have a link? (if it's NXT see below)  I've been in the Bitcoin-qt code, it's not pretty.

while ethereum has some interesting ideas, if you followed the discussion you would perhaps have different take on it.  It went something like this:



"Damn, this scripting system SUX guys!"

"ya it's got no loops or ifs, wth?"

"y u no have turing completeness?"

"can we make it turing complete?  i have big brain."

2 months later...

"we have (quasi) turing complete scripts!  now we can take over the world!"

"it's also a cloud computing platform!"

"Bitcoin is the next TCP-IP!  to arms!"



Seems to me that the cloud computing people got involved at some point and turned the thing into something it wasn't initially.

So, this project is going to take a lot of resources to do.  Developers want to be PAID, and investors want RETURNS.  It's looking very similar to Ripple at this point.  I raised this point re. Ripple many moons ago, which resulted in much consternation and gnashing of teeth:  "if it's open source, can we fork it and make our own network of XRPs? or Ethers?  Dogethereum?"  The Ripple guys didn't like that.  So if Ethereum is open source, it's possible to do this and the Ethers are only worth exactly the cost of processing power.  Something tells me though that key components of the system will not be open source- Ripple dithered on this point for some time before fully open sourcing everything(I think, it's really impossible to tell).  And basically it comes down to a key point- why is this hashing power a commodity if it serves no real purpose?  not unlike the arguments of gold bugs- gold is valuable because it's valuable, and that thinking seems to prevail at certain times and other times not.

I wrote a number of papers about p2p financial contracts before Ethereum or related projects ever even came out.  Fact is, we can do this fairly simply with something like NXT.  I think NXT is very compelling because it's a complete rewrite and the code is CLEAN java.  Innovations will happen fairly quickly in NXT(amof they ARE happening).  So we can support complex contracts simply by making the kernel modular, having a TYPE field in the TXs and the TX is processed by the module according to type.  They already have a namecoin clone and bitmessage clone in there.  No need for complex turing complete support.  Most importantly the system remains SIMPLE, PEER TO PEER, and accessible to the community.  I don't foresee Ethereum in this role.  One thing I see with this model is that it allows any sort of agreement imaginable, the fact is the users dont need or even WANT such flexibility, people want standardization in order to have fungibility.  Fungibility means marketability, and that means money generation.  Would you sign a contract written by some lawyer with terms you barely even understand?  no you wouldn't - so the number of contract types are countably finite.  We don't really NEED such a complex scripting engine, certainly if it comes at a price - simplicity.

What can we do with such contracts?  We can do financial engineering in a p2p environment.   Here's an example, the EURO that you may be holding in your hand if you live on one side of the atlantic is really a complex of debt between countries.  If any one country defaults on their obligations, then the Euro takes a hit.  It did great for a while up until the Greece incident, and I expect to see more collapse, perhaps a major collapse of epic proportions(im a Euro bear).  So if we implement the things I outlined on http://altchain, we can do things like a Euro, or create a mutual fund, because assets can be CHAINED together.  I collateralize a debt obligation, turn that credit risk into a commodity, group them together, and use this as form of payment tender for a set of e-commerce operations(that is essentially what they did with the Euro).  It's very powerful.  It can be supported in NXT 1) without any need for mining 2) fairly simple modifications save one component and I may publish that soon.  NXT has serious potential IMHO.  I was originally intending on using something called Confidence Chains, but seems pure PoS systems offer similar benefits and they are an accepted idea.

I also like Counterparty btw- but I think their future is questionable due to outside factors.  I was a critic of these block chain piggy-back ideas(eg. color coins) because they require the consent of the core bitcoin developers and in some cases the technologies interfere with the basic Bitcoin features, and I think my first lemma has been shown to be correct.  If something like Counterparty were to become widespread, it would cause a serious problem of bloat in the block chain and they would probably be forced to move to an altchain, some coalition of core devs and long-running node admins would force them off the network. In this case, they have precisely nothing on NXT(which is implementing a native CC feature).  Also some of their ideas are defective in ways that have yet to reveal themselves. 

-bm

[bluemeanie1]

also:  I notice the ethereum.org website has ZERO respect for your privacy.  They put just about every social button imaginable on there.  Clearly this thing is Silly Con Valley through and through.

http://thenextweb.com/facebook/2011/05/02/wikileaks-founder-facebook-is-the-most-appalling-spy-machine-that-has-ever-been-invented/

currently trying to find the ethereum repo, where is it?

-bm

[bluemeanie1]

so they had a link on their site labeled 'Linux Source' :



I clicked it, got a tar file and when I open it I get this?  (they also have a disclaimer on there: https://i.imgur.com/iaeKMCX.png



I dont know what this is.  It's not source code.

-bm

[Gyrsur]

*listen*

[2112]

This thread is both very interesting and very perplexing. Neither Bitcoin nor Ethereum offer a Turing-complete script execution environment.

In case of Bitcoin the limitation is enforced by the scripting language being loop-free and a limit on the length of the program. So the execution cost of the Bitcoin script is (approximately) equal to the length of the program.

In case of Ethereum the limitation is explicitly enforced by a parameter ("gas", probably meaning "petrol") to limit the energy expended on executing the script, because there isn't even approximate relationship between the length of the script and the time and energy it takes to execute it.

When I went to school everyone had to know how to transform a program to its loop-free equivalent and how that relates to the Kolomogorov complexity of the representation of the program (basically unroll all loops and compute both branches of every conditional and beware of the exponential blowout).

Thus I think the thread should be entitled something like "Script with loops or without loops (Bitcoin vs. Ethereum)". Or maybe "To compress the scripts for storage or not: that is the question!". This will better represent the discussion in this thread: it is really about tradeoff between two choices: "use lot of storage and minimally simpler interpreter" and "use much less storage but more complex interpreter".

[gmaxwell]

It isn't really a question of storage or bandwidth, since nodes are free to compress the representation they use to store (especially) or transmit to other compatible nodes. What was interesting to me is how easily/cleanly all of the ethereum examples I've seen unrolled. I'm not quite sure what I'd call it a question of... "size of the simplest serialization"?

I think the more important bit of cognition here is that what Script in a consensus system is actually doing:  99.999% of it is not computation it's _verification_ of a computation someone else performed. And verification is computationally distinct from actually computing, it's fundamentally easier.

Beyond the obvious but less practical connections to non-interactive zero-knoweldge proofs for NP statements, there are some pretty important down to earth ramifications of this.

For example, take the P2SH idea where the PubKey is a script hash and apply it recursively— so a script opcodes and interior hash nodes (you could then think of the script as a merkelized abstract syntax tree). From an implementation perspective, you can think of this as having a OP_choice which takes one serialized script and one scripthash. What you reveal to the network then is not the whole program, but just the parts covered under the taken branches, for the rest you only give their hashes. Other nodes don't care about what happened behind untaken branches, only that the branches which were taken ultimately resulted in acceptance.

Verification time then, is, as before, linear in the size of the signature.

But you've improved privacy— assuming there was enough entropy the untaken branch the public doesn't learn anything about it.

And you've removed much of the blowup in the size of the circuit from the visibility of the verifying nodes.

This kind of tool has been on my must-have-todo-list for any major revisions to Bitcoin script for since something like 2011. While looping might be a reasonable construct (though the complexity of the 'gas' stuff above is not inspiring me with confidence on that front— and complexity is very important here since it directly impacts correctness: alternative implementations of bitcoin already get script wrong over and over again, and no one is yet trying anything fancy like JIT execution of scripts) that may be worth including simply because it makes some scripts have a much more succinct serialization (e.g. consider a script implementing a lamport signature that iterates over all the bits in a hash), I think ideas like the MAST are much more interesting and more likely to be useful...

Looping isn't mutually exclusive with techniques like MAST, but there is a question of finite cognitive bandwidth.  In my opinion the only thing the looping has been really solidly demonstrated to be useful is enabling the not quite accurate and not at all relevant claim of turing completeness for marketing purposes... which itself is not even all that useful except that it enables all kinds of thoroughly confused ideas like thinking the system in question is a competitor to EC2. Misunderstanding which some promoters of some alternative systems decline to correct in what seems to be a rather convent move in terms of encouraging participation in their public investment scheme(s).

[bluemeanie1]

I'm still in the process of reviewing the 'yellow paper',  simple and p2p is NOT what this is likely to be.

He explains near the end of the paper how the scripting is used for a new sort of PoW that is resistant to commodification(the ASIC problem) and he also insinuates that the side-effect of this 'work' is somehow useful for the system(doesnt really show how this is possible).

A set of transactions, pseudo-randomly determined from the nonce value and selected from the last N blocks is taken.  N is large enough and the selection criteria are such that execution of the transactions requires some non-negligible amount of processing by the EVM. Whenever code is executed on the EVM, it is pseudo- randomly (seeded again by the nonce) corrupted before alteration. Corruption could involve switching addresses with other transactions or rotating them through in the state trie (perhaps to the next address with the same order of magnitude of funds), rotating through instructions that have equivalent stack behaviour (e.g. swapping ADD for SUB or GT for EQ), or more destructive techniques such as randomly changing opcodes. This results in a problem that both require generalised computation hardware and is sequentially memory (and perhaps even disk) hard.  Any specialised hardware to perform this task could also be leveraged to speed up (and thus drive down costs) of general Ethereum transaction processing.

does using the British spelling give you some kind of bonus points in the Bitcoin world?

I still tend to think something like NXT offers something simpler and, how should I put this: FUN?  it seems whenever VC gets invovled in these projects they turn it into something altogether incompatible with the ethos of the bitcoin world.  -bm

This thread is both very interesting and very perplexing. Neither Bitcoin nor Ethereum offer a Turing-complete script execution environment.

In case of Bitcoin the limitation is enforced by the scripting language being loop-free and a limit on the length of the program. So the execution cost of the Bitcoin script is (approximately) equal to the length of the program.

In case of Ethereum the limitation is explicitly enforced by a parameter ("gas", probably meaning "petrol") to limit the energy expended on executing the script, because there isn't even approximate relationship between the length of the script and the time and energy it takes to execute it.

When I went to school everyone had to know how to transform a program to its loop-free equivalent and how that relates to the Kolomogorov complexity of the representation of the program (basically unroll all loops and compute both branches of every conditional and beware of the exponential blowout).

Thus I think the thread should be entitled something like "Script with loops or without loops (Bitcoin vs. Ethereum)". Or maybe "To compress the scripts for storage or not: that is the question!". This will better represent the discussion in this thread: it is really about tradeoff between two choices: "use lot of storage and minimally simpler interpreter" and "use much less storage but more complex interpreter".

[bluemeanie1]

This kind of tool has been on my must-have-todo-list for any major revisions to Bitcoin script for since something like 2011. While looping might be a reasonable construct (though the complexity of the 'gas' stuff above is not inspiring me with confidence on that front— and complexity is very important here since it directly impacts correctness: alternative implementations of bitcoin already get script wrong over and over again, and no one is yet trying anything fancy like JIT execution of scripts) that may be worth including simply because it makes some scripts have a much more succinct serialization (e.g. consider a script implementing a lamport signature that iterates over all the bits in a hash), I think ideas like the MAST are much more interesting and more likely to be useful.

IMHO, the biggest drawback to this is complexity.  Building, debugging, supporting and verifying this software is not going to be cheap or fun.  Therefore it must require the involvement of investors to exist.  Can we make a simpler system that supports our needs- most certainly, I outlined it above.

Sometimes Simple Wins.  It just seems very un-Bitcoin.

-bm

[bluemeanie1]

btw- there is an Ethereum repo: https://github.com/ethereum/cpp-ethereum

haven't been able to build it though.  I do recall Ripple releasing a complex and unusable codebase as a show of face to the open source community, so as of yet Im not fully convinced.  They need to recoup *somehow*.  I assume it will be through the sale of these Ethers and maintaining a privilege over key components in the system either through typical ownership means or perhaps patents.

one way they could do this is to have the industrial strength Super Nodes running some enhanced software that is unavailable in open source.  Most of this transaction processing will not be happening on the average P2P Pete's computer.  There will be a tiered society of nodes.

-bm

[gmaxwell]

I think the complexity is manageable under certain conditions.

You have a list of operators, each has a cost. You add up the cost as you verify. Relayed transactions should carry the total cost with them, if the stated cost and the computed cost do not match exactly you reject the transaction and ban the peer.  There is currently an opcode limit in Script which is added this way, except the cost is always one and its not signaled.  A more complex opcode counter is an additional bit of consensus code you could get wrong, true, but it need not be excessively tricky, and if all transactions were carrying their own counts a counting bug would be more easily found in testing. Of course, it's best if the cost is always 1 except for a few special operations (e.g. expensive crypto operations like signature validation).

What I think really creates big challenges is when you expect the total execution time, not including single hotspots like the cryptoops, to be non-trivial. As soon as someone feels they need to diverge from the big-dumb-switch-statement style simulator  (which simply counts one each run through, and some more for certain operations) and start doing fancy template matching or JIT compilation of scripts and it becomes very easy to have hard to detect operation counting corner case bugs. But these sorts of risks can me mitigated by setting sane limits to begin with and insuring that the execution itself will never be such a bottleneck that anyone feels they need to engage in risky optimizations of consensus critical code. Since fancy (and different) execution implementations are risky regardless of things like looping operations, being mindful of complexity and avoiding the need to optimize addresses a wider set of issues than just the operation counting ones.

If things like loops actually worth doing is another question... the things I'd want to use them for in Script today can't be done for unrelated reasons.

[jonald_fyookball]

This kind of tool has been on my must-have-todo-list for any major revisions to Bitcoin script for since something like 2011. While looping might be a reasonable construct (though the complexity of the 'gas' stuff above is not inspiring me with confidence on that front— and complexity is very important here since it directly impacts correctness: alternative implementations of bitcoin already get script wrong over and over again, and no one is yet trying anything fancy like JIT execution of scripts) that may be worth including simply because it makes some scripts have a much more succinct serialization (e.g. consider a script implementing a lamport signature that iterates over all the bits in a hash), I think ideas like the MAST are much more interesting and more likely to be useful.

IMHO, the biggest drawback to this is complexity.  Building, debugging, supporting and verifying this software is not going to be cheap or fun.  Therefore it must require the involvement of investors to exist.  Can we make a simpler system that supports our needs- most certainly, I outlined it above.

Sometimes Simple Wins.  It just seems very un-Bitcoin.

-bm

I don't know much about ethereum.  But from a general member of the bitcoin community, what I'm hearing is: expensive ipo, complexity, not necessarily 100% open source, big promises...

I don't want to come off as a skeptic/cynic/hater on ethereum.  I applaud the innovative spirit
and anyone who creates something.  

[bluemeanie1]

I think you're really trivializing it.  We're talking about the building of a whole new VM emulation machine here.  There's going to have to be thread monitoring, security analysis, etc.  Think of the bottleneck we've got right now in Bitcoin-qt(as a developer of it you may not agree), this will make it 30 times worse.

We're getting away from the Keep It Simple Stupid principle here.  It is possible to have a very useful modular contract system and it doesn't require all this.  Code bloat = support costs = VC involvement = centralisation.  did I spell that right, mates?  Bitcoin is about making money creation accessible to everyone.

-bm

[bluemeanie1]

I don't know much about ethereum.  But from a general member of the bitcoin community, what I'm hearing is: expensive ipo, complexity, not necessarily 100% open source, big promises...

I don't want to come off as a skeptic/cynic/hater on ethereum.  I applaud the innovative spirit
and anyone who creates something.  

there are some intensely thought out ideas in the whitepaper.  That doesn't necessarily mean it's going to be a winner.  Sounds like another Ripple.

"All language designers are arrogant. Goes with the territory... " -Larry Wall

"not necessarily 100% open source"  and if it's anything like Ripple theyre going to do a little dance with this to keep people on the line.  Release some code, code some more privately, release a little here and there, "oh it's coming soon", "that part isn't open source", "did we say that?", etc.  Fact is there's an asymmetry here, the VCs are top down, and the community of potential users is decentralized.  Eventually though it seems Ripple lost the battle.  I heard they might be selling off to ABA or SWIFT.

-bm

[2112]

IMHO, the biggest drawback to this is complexity.  Building, debugging, supporting and verifying this software is not going to be cheap or fun.  Therefore it must require the involvement of investors to exist.  Can we make a simpler system that supports our needs- most certainly, I outlined it above.

Sometimes Simple Wins.  It just seems very un-Bitcoin.

From the purely-computer-science point of view the required interpreters, compilers, theorem-provers, etc. already exist and are well-debugged. They are available in every decent CS library under the very dirty and dusty keyword: Lisp. In one of those books there is a maxim: Those who don't know Lisp are doomed to reinvent it.

Obviously, Lisp doesn't directly plug into the Ethereum implementation. But knowing it would certainly remove lot of "fun" from reinventing the wheels for the Ethereum.