Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

OP_EVAL doesn't stop recursion #729

Closed
roconnor opened this issue Dec 27, 2011 · 28 comments

Comments

@roconnor
Copy link

commented Dec 27, 2011

Currently in the OP_EVAL processing code you have:

if (!EvalScriptInner(stack, subscript, txTo, nIn, nHashType, pbegincodehash, pendcodehash, nOpCount, nSigOpCount, fStrictOpEval, nRecurseDepth++))

The postfix ++ operator returns the unincremented value of the variable.

So my understanding is that (1) this doesn't limit the depth of recursive calls and (2) this does limit the number of non-recursive calls you OP_EVAL you have in one script.

In particular (1) implies that that Gavin's example (why wasn't this tested) of "OP_PUSHDATA {OP_DUP OP_EVAL} OP_DUP OP_EVAL" should run in an infinite loop (though I haven't tested this).

<rant>
More generally, this OP_EVAL is a very large change that clearly hasn't been vetted nearly enough. It took me all of 70 minutes of looking to find this bug. You guys are not ready to implement this. OP_EVAL turns a fundamentally Turing-incomplete langauge with clear termination conditions into what I believe an "in-principle" Turing complete language that is only held in check by hacks (which haven't even been implemented properly).

You guys need to stop what you are doing and really understand Bitcoin. In particular you should make a proper specification of the existing scripting language, ideally by creating a formal model of the scripting language. Prove upper bound on the space and time usage of scripts. Decide what bounds you want to maintain, and only then start defining OP_EVAL, proving that it preserves whatever properties you want your scripting system to have. OP_IF, OP_CODESEPARATOR, OP_EVAL all have the possibility of interacting complicated ways and you can't just hack the scripting language arbitrarily.
</rant>

@luke-jr

This comment has been minimized.

Copy link
Member

commented Dec 27, 2011

I am posting a comment here solely to be notified of other replies. Blame GitHub.

@TheBlueMatt

This comment has been minimized.

Copy link
Contributor

commented Dec 27, 2011

You could just "follow" bitcoin/bitcoin and then get all new pulls/comments/issues in a nice RSS feed (though this post is largely because I want comments to this issue in email too...)

@laanwj

This comment has been minimized.

Copy link
Member

commented Dec 27, 2011

Yeah I'd suggest against using ++ in a parameter to a function call, if only because it is unclear when reading the code.

I tend to agree with you about OP_EVAL not being thoroughly enough vetted. The code is new and there's already been one last-minute almost fatal vulnerability. I'm inclined to think that it will bring more trouble.

@gavinandresen

This comment has been minimized.

Copy link
Contributor

commented Dec 27, 2011

I'm open to suggestions on how to get code more thoroughly vetted BEFORE being pulled into mainline. In my experience, most people ignore changes until they are part of git HEAD.

RE: roconner's rant: Proving the time and space bounds of Script is a great idea-- roconner, can you make that happen? I have no idea how to do that, I have no experience with provably correct specifications/code/etc.

However, even if Script (and OP_EVAL) was proven correct, that would not stop me from writing "++" when I meant "+1".

The larger issue is "are the benefits of OP_EVAL (eventually, safer wallets, escrow, etc) worth the risks?" I think the benefits are large and the risks are manageable, and delaying the rollout by six months would just push almost exactly the same risks six months away. And we'd be six months farther from having more secure wallets and transactions.

@laanwj

This comment has been minimized.

Copy link
Member

commented Dec 27, 2011

Agreed @gavinandresen I don't think simply delaying the change would have won much. People hardly look at "non-official" branches.

Somehow we should encourage more people to take a look at the source carefully, and attack it from any angle possible. Thanks a lot @roconnor.

@roconnor

This comment has been minimized.

Copy link
Author

commented Dec 27, 2011

@gavinandresen can you (or someone else) clearly document all the desired functionality that you want from OP_EVAL, giving examples of how it would work, either in the BIP_0012 wiki page or linked from the wiki page? Maybe we can find an alternative way of getting all this functionality without such a fundamental change as OP_EVAL? OP_EVAL destroys all sorts of nice properties of the scripting system. As I said before OP_EVAL (probably) makes the language "in-principle" Turing complete. Also miners now have the ability to review the entire script before execution. These will go away when OP_EVAL is introduced. This is what I mean by a fundamental change.

@luke-jr

This comment has been minimized.

Copy link
Member

commented Dec 27, 2011

I think a good compromise would be delaying OP_EVAL on the client end, and enabling it fully on the miner end. This basically has the same net effect except that OP_EVAL transactions need a couple more confirmations before they can be trusted.

The problem with poor review of other clients/branches can be addressed by largely revamping the download on Bitcoin.org. IMO, Bitcoin.org needs to list 3 categories of clients: "well-tested for production server deployments" (currently bitcoind 0.4.x), "no major problems, safe for everyday users" (Bitcoin-Qt + bitcoind 0.5.x), "testing, please help if you can" (Bitcoin-Qt + bitcoind 0.6.x beta/rc, and MultiBit 0.2.0), and finally "experimental, it compiled, maybe it works" (Bitcoin-Qt + bitcoind "next"); giving users these options enables them to more easily provide input.

Regarding code coverage testing, I think someone really should look into LLVM's KLEE before a bad guy does, since it's pretty much guaranteed to find some bug.

As far as the code review process in general, I think it is too slow already. Protocol-level changes probably need a lot more review, but high-level ones are stagnating and wasting way too much developer time on rebasing/merging due to the slow rate of merges.

@ByteCoin

This comment has been minimized.

Copy link

commented Dec 28, 2011

@roconnor Go into more detail about these "nice properties" of the scripting system that OP_EVAL destroys and then we can talk about how important these properties are and how to preserve them.

It seems easy in principle to limit the evaluation time of scripts and forbid looping constructs by preventing recursive OP_EVALs. It's possible that in this instance it was not implemented correctly but I think it indicates a lack of resources devoted to testing rather than a more fundamental flaw.

If you felt strongly that OP_EVAL was undesirable, you should have made a bit more noise before a lot of engineering and political effort was expended traveling down this path.

Taking your words literally, you say that miners won't be able to review the entire script before execution once OP_EVAL is introduced. This is plainly false. I know the change you actually meant and it was mentioned the very first time OP_EVAL was proposed.
With OP_EVAL, it becomes practically impossible to work out what sort of script or whether a valid script exists which can redeem the proposed "standard" OP_EVAL transactions. I think this is a desirable feature rather than an unfortunate consequence.

@luke-jr

This comment has been minimized.

Copy link
Member

commented Dec 28, 2011

No, I'm pretty sure he means reviewing the entire script before execution. This is not false.

@gavinandresen

This comment has been minimized.

Copy link
Contributor

commented Dec 28, 2011

@roconnor: reasons for, and advantages/disadvantages of, OP_EVAL were discussed pretty extensively in this forum thread three months ago: https://bitcointalk.org/index.php?topic=46538.0

Initial implementation was available for code review on October 19'th, over three months ago. I know everybody is busy, but I don't think 4 or 5 months to get a new feature out is unreasonable.

@luke-jr

This comment has been minimized.

Copy link
Member

commented Dec 28, 2011

IMO, new protocol-level features probably should have at a minimum 6 months - maybe a whole year - of testing/review, with ideally at least 3 or 4 competent developers signing off as having actually read the code and given it some thought. On the other hand, new features that don't affect the protocol or implementation thereof, should be included ASAP as soon as the next merge window opens, with at least 1 other developer giving it a look over or numerous users testing and using it. In reality, many of the latter class (non-protocol-related) have been ready to this level and waiting for merging since before 0.5, some even before 0.3.24, and still aren't in git HEAD. The main difference for OP_EVAL is that Gavin is personally behind it. I understand that Gavin et al have a right to pick their priorities, but it does appear to have a bit of an extreme slant in a lot of cases.

@TheBlueMatt

This comment has been minimized.

Copy link
Contributor

commented Dec 28, 2011

I have no idea how much such a thing would cost, or if there is remotely the budget to get such a thing done, but what would people think of asking large pools, exchanges, and other interested companies to contribute to get a professional code review of new major bitcoin releases, or maybe every other release or something?

@TheBlueMatt

This comment has been minimized.

Copy link
Contributor

commented Dec 28, 2011

Also, I agree that we need a more strict set or pre-pull ACKing rules, maybe not 6 months of review, but ie a minimum of 3 ACKs from official developers before pulling, and not just I read this acks, but I at least compiled this and read it very carefully.

@luke-jr

This comment has been minimized.

Copy link
Member

commented Dec 28, 2011

An important point of my comment was the distinction between protocol-level changes and other changes.

@roconnor

This comment has been minimized.

Copy link
Author

commented Dec 28, 2011

Good morning all.

@gavinandresen @ByteCoin: I glanced through that thread a while ago (BTW, extracting the use cases of OP_EVAL from reading that thread is difficult, which is why I expected a summary of uses to be in the BIP) and there seemed to be enough skepticism in that thread and on #bitcoin-dev that I didn't expect the proposal to move forward without further consideration. Suddenly I find out from a blog post that OP_EVAL is slated for inclusion in 0.6. Since I'm not yet convinced OP_EVAL is a good idea, I went browsing through the implementation trying to find an error to stop you guys (since the OP_EVAL proposal isn't even close to documented in the BIP (how does OP_EVAL interact with OP_IF? Does OP_EVAL clear the alt_stack? what is the rational for these design choices (and I suspect the answer is that you guys haven't even considered this and are not even aware you are making design choices)) the only way to find out what the OP_EVAL proposal is is to read the code). It only took me 70 minutes to find an error.

Now I see this as a serious red flag. If I can find a bug in 70 minutes, how many other bugs are lurking? Think about it. (Granted this wasn't as serious as I reported due to the op_code execution limit, but it was still a moderate bug.)

(Also because OP_EVAL doesn't have a detailed specification, I wasn't even sure that the ++ was an error when I first saw it. Only later after double checking the semantics of post-fix ++ was I sure it was an error.)

@ByteCoin current properties include something like square or cubic space usage in terms of the length of scripts (ignoring the artificial limits imposed by the standard client) and some sort of polynomial bound on time usage that I haven't figured out. Also right now the miners have the option inspect the script before executing. They can easily count the number of OP_CHECKSIGS or whatever they want to do. Tell me, how many OP_CHECKSIGS will be executed in "OP_1 OP_HASH160 OP_EVAL"? (In a related note: Personally I would have designed OP_CHECKMULTISIG to statically take m and n in the opcode itself, but nothing can be done about that now.) There may be other nice properties that I haven't even considered.

Maybe it is okay to alter these properties. Maybe it is right to clear the alt_stack upon OP_EVAL and restore it when done. I don't know. My concern is that you guys haven't even thought about these issues. These issues certainly haven't been documented anywhere.

Personally I think you cannot even give proper consideration to protocol extensions without first given proper consideration to the current protocol by documenting it and its design. (Did you know that a OP_VERIF will cause a script to fail even if it occurs in a non-executed part of an OP_IF branch?) And yes, Gavin, I do volunteer to do this and have been slowly working on it in my spare time.

@TheBlueMatt

This comment has been minimized.

Copy link
Contributor

commented Dec 28, 2011

@luke-jr I agree there should be a distinction, though I would put the distinction more along the lines of gitian/contrib/doc/minor ui changes vs core/protocol/etc changes. Though maybe protocol changes need acks from other client devs too.

Luke-Jr reply@reply.github.com wrote:

An important point of my comment was the distinction between
protocol-level changes and other changes.


Reply to this email directly or view it on GitHub:
#729 (comment)

@gavinandresen

This comment has been minimized.

Copy link
Contributor

commented Dec 28, 2011

OP_EVAL should do exactly what it says in the BIP-- clearing the alt stack and the fExec state are bugs, because the BIP doesn't say they should be cleared.

RE: how many other bugs are lurking: who knows? That's why we code review and test, and that's why bitcoin is version zero-point-something.

I think you're losing sight of the big picture: I want OP_EVAL sooner rather than later exactly BECAUSE bugs happen. OP_EVAL and the multisignature transactions make it possible to distribute trust (in the form of private keys) between two different devices/implementations, so if one has a horrible bug that lets hackers try to spend your coins they'll be foiled by the signature required on the other.

On the big picture of Script in general: I think opcodes that are ill-defined or difficult to reason about should join the list of disabled opcodes; I have no idea why Satoshi kept OP_VERIF. Longer term, I like the idea of a well-specified little evaluation engine that is easy to reason about and is extremely well-specified, but that will take a long time to get right. Despite the bugs, I think OP_EVAL is possible to get "right enough" in the next month.

@roconnor

This comment has been minimized.

Copy link
Author

commented Dec 28, 2011

No no, clearing the fExec state isn't a bug. God have mercy on us if OP_IF statements can start in an OP_EVAL block and end outside it. I have no idea about the alt_stack. After all the alt_stack is cleared between the output script and the input script running.

@roconnor

This comment has been minimized.

Copy link
Author

commented Dec 28, 2011

@ByteCoin Long story short, OP_EVAL effectively makes static analysis of scripting code impossible, and for this reason alone I personally reject the entire proposal. But even if this doesn't bother you, the fact that OP_EVAL isn't well specified and hasn't yet been well implemented should be enough to at least delay the proposal.

@roconnor

This comment has been minimized.

Copy link
Author

commented Dec 28, 2011

@gavinandresen You make it sound like OP_EVAL is the only possible mechanism to enable distributed trust.

@roconnor

This comment has been minimized.

Copy link
Author

commented Dec 28, 2011

@gavinandresen OP_VERIF is disabled. But it is processed this way because of this code:

 else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))

OP_VERIF is in between OP_IF and OP_ENDIF so it is executed, but since there is no case handler, it fails.

My point is that this complexity is exactly the reason you need to stop expanding the protocol and figure out what you already have. Blindly going forward with OP_EVAL when you clearly don't understand the existing protocol yet is simply too risky. You may cause more problems than you solve.

@ByteCoin

This comment has been minimized.

Copy link

commented Dec 28, 2011

@roconnor and @luke-jr : Let's consider pragmatic Bitcoin development politics. We've said that "the perfect is the enemy of the good". Gavin's a good project leader and I think it's more productive to support his development vision than to second guess it and throw sand in the gears.

By far the biggest systemic risk to Bitcoin is the possibility Gavin might leave. If you disagree with him then your ultimate sanction is to leave. The weight of your opinion is likely to be proportional to the amount that you help with the project and make Gavin's life easier. If you help out then Gavin's incentivized to keep you happy or else he loses your development effort when you leave. If you want your opinion taken more seriously and have more influence in the development direction I suggest you work together. Do some work you don't particularly want to do or find interesting so that it doesn't have to be done by someone else.

I've read Gavin's implementation of OP_EVAL. He didn't do it in the way I would have done it but HE DID IT. I didn't. Similarly with large parts of the existing client and protocol. It's rubbish but it exists and works. You can criticize it but it's not very productive unless you're prepared to help.

You raise some valid points but I'll be much more impressed if you follow up. You say "these issues haven't been documented anywhere". Document them yourself (in the wiki?) You say "you guys haven't even thought about these issues". Ok you have (a few months too late but never mind). Perhaps we have and didn't bother documenting it, perhaps we didn't.

I think it's unlikely that OP_EVAL developmet will come to a grinding halt based on your concerns. Your disapproval signals a lack of appreciation for the work that has been done and is demoralizing. It's easy to find something to criticize about someone else's code. Why not be more supportive? Aren't we all working towards the same ultimate goal?

ByteCoin

PS. Thanks for finding the bug.

@roconnor

This comment has been minimized.

Copy link
Author

commented Dec 28, 2011

I apologize if I've come across as harsh. I only raise my voice loudly due to the urgency of the situation. Once OP_EVAL transactions start trickling in in a few weeks there would be no turning back and I hadn't realized before this week that OP_EVAL was so close to being deployed.

I totally respect the work that all of you have put into bitcoin. Please, don't undo all that hard work by making hasty changes.

@luke-jr

This comment has been minimized.

Copy link
Member

commented Dec 28, 2011

@ByteCoin, I think you mean the ultimate sanction is to fork... Anyhow, I've tried to make Gavin's job easier with the 'next' (only stuff the core team has approved) and 'next-test' (that plus other stuff not yet accepted) branches, but he seems to prefer ignoring them and delaying merges until he gets around to doing them himself, which makes more work for everyone.

I'd like to think I've been fair with OP_EVAL as well: it's been part of 'next' from the start, and I have support for it deployed live on Eligius; however, these recent concerns as well as areas we could improve it before deployment (such as pubkey extraction) have changed my position to one of preferring a slight delay for further improvement. I don't think anyone is suggesting it should come to a grinding halt, but that it needs more time before it's ready.

@ByteCoin

This comment has been minimized.

Copy link

commented Dec 28, 2011

@luke-jr Re: Fork vs Leave. How would we tell the difference?

@luke-jr

This comment has been minimized.

Copy link
Member

commented Dec 28, 2011

@ByteCoin: someone forking would release a new client. ;)

@ByteCoin

This comment has been minimized.

Copy link

commented Dec 28, 2011

@luke-jr And this would be noteworthy for some reason?

@genjix

This comment has been minimized.

Copy link

commented Jan 1, 2012

My thoughts: I am protocol-conservative implementation-liberal by nature. I would prefer slow and steady with the protocol rather than moving hasty. With the implementation things should be much faster in current bitcoin. 6 months is nicer than 3 for this :)

However, that's just my preference. Whoever writes the code kind of gets the say. And there's enough intelligent people discussing this on here, the forums, mailing lists, IRC and email that I trust the people involved to get it right :)

We are at a momentous exciting time for bitcoin, and there are going to be contentious issues moving forwards. We must not squander this repository of raw potential by excessively stalling. Always throughout history when moving forwards there were those who would have rather have stayed at home but had to be dragged kicking and screaming into the future.

destenson pushed a commit to destenson/bitcoin--bitcoin that referenced this issue Jun 26, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
7 participants
You can’t perform that action at this time.