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

[bluemeanie1]

"Real programmers can write assembly code in any language."

-Larry Wall

[telepatheic]

Anyway, I'm sure there's a ton of cool stuff we can think of for Script 2.0 (I'd quite like some kind of reflection abilities), but we barely exploit Script 1.0 today! It seems kind of weak to be running ahead of ourselves here.

I'm interested to hear people's thought on what can be done with the current scripting system. I've been messing around with it and it seems that there are only a few uses:

- More complex multisignature (where you set requirements on specific sets of people that can sign transactions using conditions e.g. of 5 possible keys require either (( key a or key b ) and c ) or ( key b and key d and key e )

- Proof of work (you can require the spender to do some hashing in order to spend the coins see http://blockexplorer.com/testnet/tx/44b9f9ff28fbfc33d4824729b2ec6f2929588faef81717e194fd7fe2a6b5d384 )

- Require the spender to solve simple maths puzzles (see http://blockexplorer.com/testnet/tx/de333be5247e7d9cfe564ffbd33e3c48dfaa0a818304347c6ecec51b57aef4e7 )

- Require the spender to know some additional piece of information (see http://blockexplorer.com/testnet/tx/c5c6b5582ff9d572296e7af3d6821f103f88386ee9f77ffae78c2db45816b80e )

- Any combination of the above.

The idea of solving maths puzzles is rather stupid as this can be reduced to a case of requiring the spender to know some additional piece of information where the puzzle itself is communicated out of band and this too can be reduced to a case where the solution forms a part of the private key required to spend the transaction. Alice knows private key A which has public key a. Bob knows the solution to a problem B which has public key b. Bob sends the funds to a+b and Alice must solve the puzzle to find B to find the required private key A+B.

So scripting only really allows proof of work and complex multi-signatures.

Can you suggest other uses?

[bluemeanie1]

it's really much more than just a money system.  There's people on the forums making all sorts of suggestions: "Lets make a Distributed Wikipedia!".

That one amuses me, one of  biggest reason for my interest and eventual involvement in Bitcoin is that almost a decade ago some people argued that the Wikimedia Foundation shouldn't be formed because Wikipedia should just be decentralized, not only claiming it was possible but that it could be trivially implemented. I wrote one of my trademark rants on the physical impossibility of true decenteralized consensus, as consensus is a necessary component of replicating the functionality of a singular resource as opposed to a grab-bag of assorted repositories. Bitcoin challenged that view but didn't change was was possible— my views weren't overtly wrong, Bitcoin just works under different assumptions which I hadn't considered at the time... primarily the ability to use hashcash and in-system compensation to create an incentive alignment and to force participants to make exclusive choices.  It's far from clear, and— in fact, now seems unlikely— that these different assumptions are anywhere near as strong as they are for other applications as they are for Bitcoin, and the verdict is even still out on if Bitcoin's properties are even good enough for Bitcoin in the long run.

A lot of the things I've heard that crowd talk about don't make a lot of sense to me... e.g. implementing a freestanding rent extractor which does nothing you couldn't just do locally— which is a pretty common event because in that execution environment the agent can't keep any secrets from the public. It's the sort of argument that sounds good until someone not seeped in the excitement steps up and says "The Russians used a pencil."

that certainly reflects my feeling about it.  Have you ever seen the episode of South Park about San Francisco?  I get the feeling that's what's going on here.

. Some of it would require the network to perform IO which you can't safely do in a consensus environment (except via trusted parties— and in which case you could just have them compute for you too, and thus keep your program private), and even the things which aren't impossible run into the pointlessness problems that some of the verifiable computing stuff does: e.g. you can ask something else to compute for you, but with millionfold overhead and a loss of privacy that makes it pretty pointless to do in almost any conceivable circumstance.

absolutely.  Consider that the BTC block chain size is thought to be problematic going forward, can you imagine what this thing is going to look like?  And they contend that it will be manageable, but something tells me they assume it will not and of course, who are you going to buy a 'solution' to this problem from?  Of course it will need all sorts of expensive management units and dedicated hardware and what not, and wait... this is peer-to-peer?  They have already admitted that most nodes will not be computing the entire chain.  I would guess only a small fraction of heavily built out nodes could possibly manage this computation.

Though I'm still glad people are excited about some novel ideas.  I hope that excitement lasts once people realize that that they're not going to make it rich off of them … I hope that making the world a freer, safer, and more interesting place is enough of a motivation to retain some of that excitement. Although 15 year long winter of the cipherpunks movement suggests that some cynicism here is justified.

and when did that winter begin?  precisely with the advent of Wired magazine(who featured the Cypherpunks on one of their early issues) and the Silicon Valley VC Tech Complex who discovered that they can do the job of our spying agencies by selling us neato tracking devices that have Flappy Bird on them.  It's fairly obvious this crowd is behind Ethereum.  Of course no one seems to know where the money is coming from and the thing is populated with the typical fresh faced tech kiddies whom you would never suspect are doing anything but improving the world for the greater good.

Is all the new interest because people hadn't been exposed to these ideas— they'd never stumbled into tools like rpow or mixmaster years ago— or is it mostly because they think it's something they can cash in on? Not that I begrudge people making money, and a few will— no doubt— make a bunch, but most will not, and if its a primarily a profit motive sustaining this interest then I expect we'll have a return to the low level of progress that other tools in this space have had since the excitement in the early 90s.

I think it's a combination of opportunism and naiveté.  Sometimes I think they generate this excitement precisely to distract from those who are doing important work- and they Cypherpunks WERE important, they ARE important... but the allure of material gain seems to take precedence over idealism.

-bm

[Brangdon]

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.

That's a relatively centralised approach, though, in that the NXT core developers have to agree what the TYPE field means, and approve the code that goes in to support it. I imagine a goal of Ethereum is to allow permissionless innovation. They don't want arbitrary limits on scripts and they don't want application developers to have to get permission from anyone before they deploy. It's similar to the Bitcoin vision where you don't have to get permission from a credit card company before accepting payments.

[bluemeanie1]

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.

That's a relatively centralised approach, though, in that the NXT core developers have to agree what the TYPE field means, and approve the code that goes in to support it. I imagine a goal of Ethereum is to allow permissionless innovation. They don't want arbitrary limits on scripts and they don't want application developers to have to get permission from anyone before they deploy. It's similar to the Bitcoin vision where you don't have to get permission from a credit card company before accepting payments.

true points, but consider that the TYPE could itself be very flexible while we still have the ability to support more simplistic contracts without all this dross.  We have the ability to install a scripting engine.

consider that, under the proposed model of ethereum,

1) every node will have to process every single transaction and event of every DAC, currency ledger, decentralized wikipedia article, or what have you.  Just consider what this ledger actually looks like in their vision.

2) every transaction could take up any amount of processing power according to the amount of Gas spent.  Now keep in mind the economic model makes no sense, I pay to have my big transaction live on the network, but me- mr. Node admin dont necessarily get paid to validate that huge transaction.  They've changed the economic model by introducing limitless scripts(quasi turing complete) but they still have not found a model in which this makes sense.  It might appear nifty at the outset, but eventually this ledger will get bigger and bigger and most nodes will just go SPV, and this event wouldnt necessarily pose any problems for Ethereum Inc., actually it's better for them.  TL; DR  Ethereum can't be P2P.

3) all these transactions are PUBLIC.  Now who would want that??  see my last comment.

-bm

[bluemeanie1]

btw- someone just sent me this, it's the NXT Transaction Engine Spec:  http://ciyam.org/nxt/nxt_auto.html

note: rumor has it the author of this document has 'gone rouge' and is not involved with NXT anymore.  Is he working for Ethereum?

-bm

[bluemeanie1]

an example of the sort of 'solutions' to the problem Ethereum ideas pose:

I think ultimately what you will see is more pooling. You can sign up to a pool where you simply contribute CPU shares for portions of the work that get farmed to you, which is not the entire work of the block, but just the execution of say 10 contract messages in that block. Or you contribute storage, which is not ALL the storage, but a subset which the pool operator can request from you as they need it. These sorts of schemes still erode the decentralization, but they are a step forward from the status quo.

again some of these suppositions do not account for all the issues of processing this absolutely enormous 'global state' (like a UTXO but much more frightening).  If we do need to distribute this over many machines, absolutely at this point in time not only do we lack the software for doing so- we lack the THEORY for managing this task.  These guys are just in outer space here.

-bm

[gmaxwell]

These sorts of schemes still erode the decentralization, but they are a step forward from the status quo.

I can't figure out how that was supposed to be an improvement to the "status quo" (presumably in Bitcoin). Truly decentralized mining works fine today though its not currently very popular, that text is talking about a world where it isn't economically possible.

Moreover, even accepting the motivation the solution sounds like a handwave in other ways as well: Pooling allows work delegation because of the huge ratio of work for solving vs verifying.  Script work is all verification, barring complex and insanely expensive things like proofs of computation the best I think you can do there is farm the work out to N miners and ask for the hash of the execution transcript, and if there are disagreements verify for yourself... but even that fails if the N miners are sibyls and it has N fold overhead. What am I missing here?

[bluemeanie1]

These sorts of schemes still erode the decentralization, but they are a step forward from the status quo.

I can't figure out how that was supposed to be an improvement to the "status quo" (presumably in Bitcoin). Truly decentralized mining works fine today though its not currently very popular, that text is talking about a world where it isn't economically possible.

Moreover, even accepting the motivation the solution sounds like a handwave in other ways as well: Pooling allows work delegation because of the huge ratio of work for solving vs verifying.  Script work is all verification, barring complex and insanely expensive things like proofs of computation the best I think you can do there is farm the work out to N miners and ask for the hash of the execution transcript, and if there are disagreements verify for yourself... but even that fails if the N miners are sibyls and it has N fold overhead. What am I missing here?

they do employ something like a 'hash of the execution transcript', the whitepaper mentions the hashing of the global state.  The simple fact is they don't have any of these things worked out, and either they've got people excited about a quasi-p2p contract engine or those people are just 'paid picketer' types(I suspect some of that is going on).

most of the meat of this thing is going to be figuring out how to somehow involve and incentivize this massive distributed computation. They act as though this problem is solved, and perhaps it is- but not in a p2p way.  I can't even see how on earth people are going to want to maintain this massive block chain on their own PCs.  It's simply not clear at all how they make it feasible and attractive for people to download this chain and verify blocks, it's quite a different economic function from Bitcoin because in Bitcoin, the work is the hashing.  Here the work is the actual transaction verification itself(presumably in addition to the SHA256).

They simultaneously talk about how great and powerful these features are while trivializing the huge distributed computation problems they imply.

-bm

[Brangdon]

consider that, under the proposed model of ethereum,

Yes, when I first read their stuff I found it terrifying. Each address is like a little computer, with local state, exchanging messages with other addresses, all within the block-chain. Nice academically, but seeming like a horrendously inefficient way to do computation. It made me think of trying to compute with 1-dimensional finite state automata, or Conway's Game of Life. I get the appeal but I don't think it's practical.

[bluemeanie1]

consider that, under the proposed model of ethereum,

Yes, when I first read their stuff I found it terrifying. Each address is like a little computer, with local state, exchanging messages with other addresses, all within the block-chain. Nice academically, but seeming like a horrendously inefficient way to do computation. It made me think of trying to compute with 1-dimensional finite state automata, or Conway's Game of Life. I get the appeal but I don't think it's practical.

ya it does somewhat conjure up the Wolfram works doesn't it?

the basic problem is this: entropy(σ-state) = O(∞). 

where σ-state is Ethereum's expanded UTXO concept.  in english: the application state has infinite information in it.  In addition they lack a useful economic model that offers an incentive for nodes to either store, manage and compute sigma.  They've got their wires crossed concerning PoW concepts and the work it takes to compute σ.  In bitcoin entropy(σ-state) = O(num accounts) (just eyeballing that).  Although gmaxwell has made some progress in understanding how this works: https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas



-bm

[go1111111]

Gregory is right, MASTs seem like a very reasonable way to allow larger programs to be built without causing huge blowup inside the chain, and being able to hide parts of the program opens up interesting possibilities for carefully constructed contracts.

Can someone define what MAST means in this context, for the benefit of the newbs? It's a tough term to search for.

[mmeijeri]

Merkelised Abstract Syntax Tree. Its root hash gives a summary of the whole AST, just as with a Merkle root in a block. This allows you to give the part of the script that is actually executed when spending, without having to list the whole possibly very lengthy script while still proving you've only used branches from the original AST.

[UnunoctiumTesticles]

Hope it is not too late to get some feedback on my thoughts.

My take away from the upthread is consistent with my own analysis—centralization of pools is probably positively correlated with required computation (above some threshold).

The Ethereum applications seem important and reasonably decentralized.

https://github.com/ethereum/wiki/wiki/White-Paper#applications

So pray tell me why it isn't superior to have merge-mined chains for new contract types (as we think of them) and optimize those chains rather than a generalized VM on one block chain?

Advantages are:

• Centralization is granular per contract type.
• Mining participation is optional, thus chains can compete instead of the swallowing the universe entropy(state) = O(∞)
• Failure modes are more contained.
• Incremental development and optimization.
• Market-based instead of top-down metrics (e.g. Ethereum's gas fees) as chains compete to reward miners.

Etc.

Maybe we need to make the process of starting and publicizing a merge-mined chain easier? Do we need an app store of merged-mined chains?

P.S. Apologies in advance if one post can evaporate a $36 million market cap.

Edit: even if you did want a generalized VM for those contracts which don't have enough economy-of-scale to be their own merge-mined chain, you could make that chain merged-mined. You could make variants and let the market decide which one is the winner. Perhaps Ethereum should do this, if they are not satisfied with the Bitcoin mining structure.

[JorgeStolfi]

If CPU usage to verify a transaction is NOT related to the transaction size, then you open yourself up to denial-of-service attacks. Like:

Create an Ethereum transaction with a (huge!) fee that will pay for 60 seconds of CPU execution time.
... but craft it so execution takes 61 seconds (or, heck, make it an infinite loop, maybe you'll tickle a bug in the execution termination code).

Now broadcast it.  It will be rejected for insufficient fee, but only after peers have wasted 60 seconds of CPU time. And if the transaction is rejected, the attacker won't pay the fee.

Sorry if this has been addressed before:

In Ethereum (or in Bitcoin with Turing-complete scripts), could this idea be used by a miner to delay competing miners, rather than sabotage the network with a DDOS-type attack?

Namely, the malicious miner creates a transaction with a script that takes a long time to complete, and a fee that forces it to be included in the next block; and computes the script's outcome before issuing it.  Would that give him an edge over other miners?   

[JackH]

Seems like Pieter Wuille's Tree Signatures does alot of what we wanted without relying on Turing complete scripts like Ethereum. https://blockstream.com/2015/08/24/treesignatures/

I still dont get the turing complete argument in the Etheretum project and it seems like a waste of computing resources to go down the route they propose.

[thacypha]

How come you guys did not know BitCoin was Turing complete?

[Gyrsur]

How come you guys did not know BitCoin was Turing complete?

https://bitcoin.stackexchange.com/questions/25427/the-bitcoin-scripting-system-is-purposefully-not-turing-complete-why