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

[bluemeanie1]

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.

believe it or not I actually know how to use Lex and Yacc!  LOL.

still though, the project has a budget.  They've clearly got a sizeable marketing budget.  Have yet to see any Ethereum marketroids on here, perhaps soon...

-bm

[maaku]

Lisp is actually not ideal here. Some sort of stack-based language with strong static typing would be an optimal choice (see, for example Kitten & Joy). But yes, Ethereum is re-inventing a square wheel here.

[bluemeanie1]

Lisp is actually not ideal here. Some sort of stack-based language with strong static typing would be an optimal choice (see, for example Kitten & Joy). But yes, Ethereum is re-inventing a square wheel here.

maybe a derivative of Forth that doesn't have conditionals or loop statements?  that would make things much more manageable.

-bm

[gmaxwell]

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.

To add loops to script.cpp in the simplest way that achieves the goal in a hardforking change is that you add a "jump opcode" to the big switch statement which, if executing, changes the instruction pointer to a new value within the size of the script and continues execution. The patch is roughly four lines of code. Thats it, no "thread monitoring" (there is already an operation counter that will halt execution if more than 201 steps are taken), no "whole new VM", etc.

Like any change to the consensus code— which is a cryptosystem— It would, of course, require extensive review and to make it efficient you'd want to do as I said with making the nOpCount explicit, turned into a soft-forking change, or not be quite so ugly as a bare loop, etc. so a real implementation would be moderately more complex, but not like you seem to be thinking. Perhaps people in altcoins are proposing far more complicated things, but the currently published ethereum code (the older stuff that has almost nothing to do with their recent whitepapers) is pretty much precisely this "simplest thing" which I described above.

Now all the other things some people are talking about... I mean, some of these pure-whitepaper altcoins advertise features which I believe are impossible while their authors seem to have no concern that they might not be. About that stuff, who knows? But looping? Looping is not _that_ big deal it's also not obviously (to me) all that valuable either. "Meh."

[2112]

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.

The way you describe it, I'm not sure I understand you properly. To me it reads somewhat like: a dynamic linker of scripts that uses late binding. Unlike conventional ld.so it does it not by name but by hash of the "_text" section.

Verification is then optimized because the actual linking wasn't really performed.

But getting back couple of pages to the requirements of resistance to DoS attacks (stated by Gavin), you'll still have to design your interpreter to be able to defend itself against somebody implementing a factorial or even an Ackermann function using the mutual recursion of a set of P2SH.

maybe a derivative of Forth that doesn't have conditionals or loop statements?  that would make things much more manageable.

In light of P2SH it would be more like "stack of Forth derivatives" not a "single Forth derivative".

Lisp is actually not ideal here. Some sort of stack-based language with strong static typing would be an optimal choice (see, for example Kitten & Joy). But yes, Ethereum is re-inventing a square wheel here.

I'm not trying to say that Lisp is ideal. But in school I had to maintain both Forth and Lisp interpreters and deal with the bugs and improvement requests. Lisp tends to bunch all the pain at the beginning of the project. Forth projects start easily but continue to bleed you later on.

If you consider a task: "write a program in language X that takes another program in language X and transforms it in a certain way or verifies if it satisfies a certain condition" then for X == Lisp those programs tend to be the shortest or have already been written and debugged. This is the reason why I advocated Lisp for scripting in cryptocurrencies.

[maaku]

But getting back couple of pages to the requirements of resistance to DoS attacks (stated by Gavin), you'll still have to design your interpreter to be able to defend itself against somebody implementing a factorial or even an Ackermann function using the mutual recursion of a set of P2SH.

Why? The interpreter is already protected against this. Once the opcode limit is exeeded, the execution terminates, the transaction is rejected, and the peer is DoS banned.

Lisp is actually not ideal here. Some sort of stack-based language with strong static typing would be an optimal choice (see, for example Kitten & Joy). But yes, Ethereum is re-inventing a square wheel here.

I'm not trying to say that Lisp is ideal. But in school I had to maintain both Forth and Lisp interpreters and deal with the bugs and improvement requests. Lisp tends to bunch all the pain at the beginning of the project. Forth projects start easily but continue to bleed you later on.

If you consider a task: "write a program in language X that takes another program in language X and transforms it in a certain way or verifies if it satisfies a certain condition" then for X == Lisp those programs tend to be the shortest or have already been written and debugged. This is the reason why I advocated Lisp for scripting in cryptocurrencies.

Stack-based does not mean Forth. Just like LISP does not mean Common Lisp.

I suggest you look into Joy, Cat, Kitten, or one of the many other newer generation "concatenative" languages.

[gmaxwell]

Why? The interpreter is already protected against this. Once the opcode limit is exeeded, the execution terminates, the transaction is rejected, and the peer is DoS banned.

Yep. The only issue there that I'm aware of is the issue of priority calculation... but there are straightfoward ways to address that.

[2112]

Why? The interpreter is already protected against this. Once the opcode limit is exeeded, the execution terminates, the transaction is rejected, and the peer is DoS banned.

So in other words in Bitcoin the equivalent of Ethereum's "gas limit" is a single #define (or const int)?

Stack-based does not mean Forth. Just like LISP does not mean Common Lisp.

I suggest you look into Joy, Cat, Kitten, or one of the many other newer generation "concatenative" languages.

Some links and concrete examples of advantages from you would be helpful. There is a lot of newfangled research in front-ends that I admittedly don't follow because I care too much about back-ends and overall quality and breadth of the implementations.

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

To add loops to script.cpp in the simplest way that achieves the goal in a hardforking change is that you add a "jump opcode" to the big switch statement which, if executing, changes the instruction pointer to a new value within the size of the script and continues execution. The patch is roughly four lines of code. Thats it, no "thread monitoring" (there is already an operation counter that will halt execution if more than 201 steps are taken), no "whole new VM", etc.

Like any change to the consensus code— which is a cryptosystem— It would, of course, require extensive review and to make it efficient you'd want to do as I said with making the nOpCount explicit, turned into a soft-forking change, or not be quite so ugly as a bare loop, etc. so a real implementation would be moderately more complex, but not like you seem to be thinking. Perhaps people in altcoins are proposing far more complicated things, but the currently published ethereum code (the older stuff that has almost nothing to do with their recent whitepapers) is pretty much precisely this "simplest thing" which I described above.

Now all the other things some people are talking about... I mean, some of these pure-whitepaper altcoins advertise features which I believe are impossible while their authors seem to have no concern that they might not be. About that stuff, who knows? But looping? Looping is not _that_ big deal it's also not obviously (to me) all that valuable either. "Meh."

correct me if I'm wrong here, but it seems like you're suggesting just put a bound on the number of FLOPS, and if you exceed that they you pull some trigger that says 'BAD TX!  Dos PEER!', or some sort of punitive response.

this will give you the basic ability to loop, sure.  But as you say upgrading the script OPCODE set will be a significant deployment effort, so maybe it's best to go whole hog and group it with other desired features.

-bm

[bluemeanie1]

btw - gmaxwell, gave some more thought to your points.  I think you need to read into the latest from Ethereum.  It's a lot more than just expanding the OPCODE set.  They have a random access memory system there and other functions available to the script environment.  It's a LOT more than just expanding the OPCODEs.

I think that doing DAC properly certainly would require something like this and in that sense it's good.  Every corporation has it's own distinct operator agreement thus we would need a way to define those rules on a per DAC basis.  But perhaps there are easier ways to do this?  I wonder if we can re-purpose Java bytecodes?  Not only do you get lots of tools, lots of existing community, lots of existing security and credibility, but the engine runs natively on Android.

so the basic question is do these break anything, and can we ascribe a 'gas' price to each code?  If we can do that, we can get something like a EVM for cheap- that gives up instant compatibility with a lot of platforms.  There are other functions as well that are required.

Also I think there are some holes to some of their premises, certainly has ramifications in the realm of 'but is it Peer to Peer'?  one thing I heard them say is 'you can turn off the script engine...', implying that we leave the heavy lifting up to 'professional nodes' - essentially disenfranchising most p2p network users, which isn't very p2p is it?  there is a solution to this but I won't say for now.

Also it seems that they were trying to achieve a way to have the Work in the PoW be something useful, they intimate this in various parts of the paper, however didn't achieve it.  So for now, it's a beefed up scripting engine for Bitcoin(they also updated the algorithm using something called GHOST).

Also I suspect many parts of this wont be open source.  Expect to see lots of smoke and mirrors here.

-bm

[bluemeanie1]

also an interesting prospect: we already have Java-bytecode specific hardware, not only in Android but there was PicoJava.  http://en.wikipedia.org/wiki/PicoJava

so if Bytecode can be TX scripts, we've got a lot of stuff out of the box.  No need for VC, everything stays 'community'.  There are also open source implementations of the JVM.

-bm

[Mike Hearn]

I really don't think Java bytecodes would be appropriate for a cryptocurrency. It's a tool designed for something entirely different.

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.

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. The right place to invest at the moment IMHO is other parts of the toolchain, to make it really easy to build slick usable GUI apps that can manipulate contracts. That's what I've been working on with bitcoinj + the wallet-template app. Good cross platform APIs + lots of documentation + reusable templates to speed up development all give bigger wins right now that a more powerful scripting language, IMO.

[bluemeanie1]

Well to clarify, Java might be USED for a specific purpose today, but the original intention was to have little bits of executable code flying around the internet that are dynamically dispatched and executed.  This vision never really seemed to happen and instead we got a enhanced C("write once run anywhere") vision.

the fact is that Java bytecodes are very similar to what Ethereum has.  It's officially a "C like language" ... sound familiar?  Perhaps we could use a subset of the bytecodes?  I'm just trying to think of ways to get this functionality for cheap.  You can already see the ivory tower being constructed over at Ethereum.

So you could create a custom compilation environment that prohibits access to most of the System classes, and instead you get a very small feature set of functions(store value, check balance, etc.).  And then you get what Ethereum gives you, plus it's supported already on millions of devices and just about every computer.  They've got a couple of other things in there that would also need to be added- some complex of crypto functions on the opcodes.  I also suspect they've patented some of these ideas.

-bm

[Mike Hearn]

I'm a big fan of the idea of revisiting Java mobile code at some point as there are now JVMs that are possibly simple enough to be secure with a heavily restricted class library. But not for cryptocurrency. It's just not needed and the format evolves faster than what we really need. Also it's needlessly verbose and hard to compile for no real good reasons. You'd do it quite differently if you redesigned it from scratch.

IMO evolving Script slowly and carefully is a way better path than trying to reuse Java.

[bluemeanie1]

have you looked at Ethereum?   It's certainly not as complex as Java, but it's coming close and certainly as things progress there it will get more complex.  People have made specialize byte-code compilers before.  It would be interesting if someone could do a comparison of EVM opcodes and JVM opcodes.  Again the goal here is - how can we get this cheap?

I do somewhat agree, we don't need all this- but a new VM execution environment?  that just seems like a problem that was invented specifically so someone could solve it and make money with it.

-bm

[Mike Hearn]

Well I'm not sure Ethereum should have such a complex VM either :-)

As an example, JVM bytecodes are extremely verbose because it maps one class to one file and then uses strings to link them together. Dalvik solves that. Also JVM bytecode is for a stack machine that then has to be compiled down to register allocation on the fly at huge cost and complexity. You could do register allocation up front for a bunch of different register counts and simply the VM considerably. Dalvik also does this.

[bluemeanie1]

here's an example of an Ethereum script:

if !contract.storage[1000]:
    contract.storage[1000] = msg.sender
    contract.storage[1002] = msg.value
    contract.storage[1003] = msg.data[0]
    contract.storage[1004] = msg.data[1]
    return(1)
elif !contract.storage[1001]:
    ethvalue = contract.storage[1002]
    if msg.value >= ethvalue:
        contract.storage[1001] = msg.sender
    datasource = contract.storage[1003]
    dataindex = contract.storage[1004]
    othervalue = ethvalue * msg(datasource,0,tx.gas-100,[dataindex],1)
    contract.storage[1005] = othervalue
    contract.storage[1006] = block.timestamp + 86400
    return([2,othervalue],2)
else:
    datasource = contract.storage[1003]
    dataindex = contract.storage[1004]
    othervalue = contract.storage[1005]
    ethvalue = othervalue / msg(dataindex,0,tx.gas-100,[datasource],1)
    if ethvalue >= contract.balance:
        send(contract.storage[1000],contract.balance,tx.gas-100)
        return(3)
    elif block.timestamp > contract.storage[1006]:
        send(contract.storage[1001],contract.balance - ethvalue,tx.gas-100)
        send(contract.storage[1000],ethvalue,tx.gas-100)
        return(4)
    else:
        return(5)

so basically you need to compute this script on the current 'global state' and hash it to verify the transactions(as I understand it).  It's certainly coming close to Java in it's complexity.  I imagine that it's optimized for object-code size and perhaps some other features.  Again what I think they might be ignoring is what it's going to take to support this and community acceptance.  Ripple had some good, 'correct' ideas but the community didn't like it.

-bm

[bluemeanie1]

Well I'm not sure Ethereum should have such a complex VM either :-)

As an example, JVM bytecodes are extremely verbose because it maps one class to one file and then uses strings to link them together. Dalvik solves that. Also JVM bytecode is for a stack machine that then has to be compiled down to register allocation on the fly at huge cost and complexity. You could do register allocation up front for a bunch of different register counts and simply the VM considerably. Dalvik also does this.

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

I think it's really just an impractical use of this basic concept of a block chain.  I think they're getting carried away.  They seem to ignore the fact that in order for this to be truly p2p, every single node must execute that script and perhaps millions(or billions of them).  Of course this isn't a problem if you plan to sell the high end gear that makes this possible.  I remember for instance when color coins was at the peak of public interest there was an IBM guy hovering around, presumably he saw a market for IBM hardware there.

-bm

[bluemeanie1]

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

[gmaxwell]

btw - gmaxwell, gave some more thought to your points.  I think you need to read into the latest from Ethereum.  It's a lot more than just expanding the OPCODE set.  They have a random access memory system there and other functions available to the script environment.  It's a LOT more than just expanding the OPCODEs.

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.

but we barely exploit Script 1.0 today!

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.

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