Topic: Turing complete language vs non-Turing complete (Ethereum vs Bitcoin) (Read 34821 times)

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

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

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.

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?   

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.

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.

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

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

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.

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

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?

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


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

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

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

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.

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.


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.


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.


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

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?

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

-Larry Wall

I know they have, I was just responding to their form of "turing completeness" and not the other things. I guess we were talking past each other, sorry for that.

As far as the other things go people often don't realize that some of these mechanisms are not actually necessary and can be achieved in other ways. E.g. you don't need global "random access memory" if scripts can introspect their transactions enough to ensure that their final state is passed on in outputs— E.g. "exactly one of the outputs must be a copy of this script, plus the updated state".  Encapsulating state in this way creates good architectural isolation and makes it very easy to correctly implement reorganization logic and understand what will happen under reorganization. Obviously preserving the architecture matters a lot when you're talking about enhancements to an existing system, but the trickiness of reorganization means that I'd probably still adopt this kind of state management approach even in a totally greenfield environment. I am far from convinced that many of the people working on altcoins are even dimly aware of all the bullets Bitcoin has dodged in its design, even the ones which have been pretty widely discussed.

Likewise, any "non-deterministic" inputs to a script (such as "locktime must be at least this high") can be made deterministic by just including the input directly in the ScriptSig and having part of the criteria in the ScriptPubKey verify them.

Exactly. I am probably more enthused about the possibilities than most, but intellectual honesty keeps me from arguing for a bunch of new features in light of the reality that what we have today is hardly used at all even though it very much could be from the perspective of the technology itself. No matter how sexy I think more expressive power might be, I can't argue for it with a straight face when we're not using what we have.  It _might_ be the case that there is an expressiveness gap where we're not quite expressive enough to get more use, but I'm seldom hearing "I'd like to do X but can't but for missing Y." and often when I do hear that we're able to find a way around it (e.g. the lottery transactions). As a result I do think that any script enhancement needs to come along with an actual application (even if its only command-line geek grade) so there is some evidence that it would get used, in addition to checking all the boxes

I have a personal Script-2.0 laundry list that I've maintained for some time (but not currently published because I'm sick and tired of white-paper only altcoins taking ideas I've invented or promoted and selling them for a profit and not even implementing them!). Something like 1/3rd of the document describes contracts which tie into the features I suggest and which I think must be implemented to prove the design wisdom of an attempted implementation of the features.

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.". 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.

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. 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.

It's not unlike the Bitmessage mentality.  Bitmessage doesn't really give you much(or any) security over that of PGP, Enigmail and Anonymizers... but the devs don't want to hear it.  It's like when people discover how a block chain works they want to use it for everything, and the fact is we've got tools for secure messaging and they've been around for a while. 

There's a old saying in tech circles: "when you learn how to use a hammer, everything becomes a nail.".

-bm