top-stack item -- definition of OP-codes for Bitcoin scripting

[smtp]

Hi

I know the only reference for the bitcoin scripting at https://en.bitcoin.it/wiki/Script. There several opcodes define their action depending on the value of the top-stack item.
Thus my question: what shall these opcodes do if there is no top-stack item (empty stack)? Or is the stack always assumed to be of infinite depth (assuming always 0 (I guess then) as the initial values of the descending stack-chain) ?

Thx for clearifing
smtp

[grau]

If operands are not available for an operator, that means the script is invalid.
Better not assume anything. For certainty, read the Satoshi code.

I also started reading the wiki but there are lot more subtle features in the Satoshi code than described there.
It is very painful to achieve highest level of compatibility with it. My implementation passes the unit tests
for valid and invalid scripts as used by the Satoshi code. You might read that for starter as it is far easier to understand.


https://github.com/bitsofproof/supernode/blob/master/src/main/java/com/bitsofproof/supernode/core/ScriptEvaluation.java
 

[etotheipi]

Anything that doesn't meet the expectations of the OP-code results in an invalid script.

If it takes two values and there's 0 or 1 values on the stack -- bail and return SCRIPT_INVALID
If it checks a signature using the top stack item as a public key, but the stack data does not parse as a public key, return SCRIPT_INVALID
If there are no more opcodes to run and the top stack item is not OP_TRUE, return SCRIPT_INVALID (I think I remember that's how it works...been a while...)
etc

There are lots and lots of subtleties.  Things like this comment I found in my script processor:

Code:

       # Gavin clarified the effects of OP_0, and OP_1-OP_16.
      #       OP_0 puts an empty string onto the stack, which evaluates to
      #            false and is treated by HASH160 as '' (length=zero)
      #       OP_X puts a single byte onto the stack, 0x01 to 0x10

I have most of the opcodes testing in Armory except for th OP_IF/OP_ELSE/etc.  But honestly, you should only use that like Wikipedia -- it might help you understand it, but there's not guarantee it's actually correct (I never even ran those script tests referenced above, because I had written this script processor before those tests were made [but I did have my own less-exhaustive unit-tests]).  You pretty much have to go with Satoshi code or nothing if you want to make sure you're 100% compatible.

[gmaxwell]

You might read that for starter as it is far easier to understand.

It is however not correct and complete, and if you imitate grau's code as it currently stands you will not be compatible with Bitcoin.

[grau]

You might read that for starter as it is far easier to understand.

It is however not correct and complete, and if you imitate grau's code as it currently stands you will not be compatible with Bitcoin.

Point me to a bug in it, please.

[gmaxwell]

You might read that for starter as it is far easier to understand.

It is however not correct and complete, and if you imitate grau's code as it currently stands you will not be compatible with Bitcoin.

Point me to a bug in it, please.

I think you're failing to understand your responsibility in creating an alternative implementation.

As far as I can tell you're not even attempting to find the incompatibilities.   Requiring me to do unpaid auditing of every (sometimes pointless) reimplementation that shows up does not scale. Ensuring compatibility is actually _most_ of the effort required to create a Bitcoin implementation, and so effectively— though I'm sure you don't intend it— by releasing incompatible code and encouraging others to imitate it you're actually attempting to externalize most of your development costs onto me.  We need to find a better way to ensure the quality of alternative implementations.

(You aren't unique in this, MatthewLM's implementation is also incorrect. But at least at the moment I've found fewer issues with it than yours)

My complaint isn't simply that I know your implementation is incorrect— it's that it hasn't had the care and effort applied to make it correct.  At least right now I know that it's wrong, if I simply point out some issues then it will _still_ probably be wrong, since it still will not have had enough care and effort applied— but we won't be able to tell.   Right is better than it's-wrong-and-I-know-it which is better than it-might-be-wrong-and-we-have-no-idea.

Right now the best I can offer is that I'll keep checking and will tell you when you've finally created and/or used tests strong enough to detect your mistakes and have fixed the ones that I'm aware of.  So long as your implementation is still in development and no one has to use it, I believe this path will result in the best long term outcome for everyone— since the tests that find what I know will likely turn up problems that I don't know about.

[grau]

As far as I can tell you're not even attempting to find the incompatibilities.

I just worked several days to successfully pass all script tests the bitcoind source tree has to offer.

Requiring me to do unpaid auditing of every (sometimes pointless) reimplementation that shows up does not scale.

I do not require you to do anything. I politely asked to substantiate your claim, and I also understand that you do not have to.

[gmaxwell]

I do not require you to do anything. I politely asked to substantiate your claim, and I also understand that you do not have to.

I can substantiate it without losing the value of the evidence— Mike (TD) and I have both told you about validation flaws in your software, so it's not just me telling you this.  If you believe both of us are mistaken, we could pick a third person, I suppose. If we can find someone suitable who is willing and who actually understands the nuance.

You make me have to do _something_ when you endanger the currency I depend on by suggesting other people copy your known-to-me-to-be-incorrect code.

I just worked several days to successfully pass all script tests the bitcoind source tree has to offer.

I'm really glad to hear that you're actually working on that. I hadn't seen that effort.

As pointed out before, the unit tests included with bitcoind are not intended or adequate for this purpose, they don't even achieve full branch coverage of the script code. Bitcoin-qt doesn't even limit the testing to just those tests and it has the totally unfair advantage of being derived from the original reference implementation (so any not newly introduced bug is the normative behavior)— Bluematt's bitcoinj block tester is much more through and its also used for testing the reference client.

Perhaps we could collaborate on raising money for a bounty effort to enhance bluematt's tester to have better coverage. I'd be willing to personally chip in some coins on the condition that the bounty result ends up (1) paying bluematt some (as he already did an enormous amount of work on that tester), (2) achieve complete branch coverage in script.cpp for the reference client, (3) the tester work on at least bitcoinj/your code/the reference client/and matthewlm's code.

[grau]

I'm really glad to hear that you're actually working on that. I hadn't seen that effort.

I would suggest to take a look, but that seem to offend you.

Bluematt's bitcoinj block tester is much more through and its also used for testing the reference client.

I will work to deploy also those tests to my implementation.

I understand that you are deeply concerned of your investment. My opinion is that my work contributes to appreciation of that investment, just as it does to mine. I believe that I am not working on a pointless re-implementation, but performing the long due reengineering of a proof of concept code, so it will enable innovation and not protect but multiply our wealth.

There is the danger of a fork but also a bottleneck on innovation imposed by a monolithic, archaic and hard to maintain code base that fails to separate concepts of communication, validation, archival, wallet, mining ... Imagine innovation that could be unlocked e.g. for wallets or data mining if it were not all part and tightly coupled within the sacred code and therefore feared to be touched.

I think the best way to avoid people writing competing implementations of a great and open idea is creating and maintaining an implementation they find welcoming in design hence build onto. bitcoind is rather badly suited on that measure. No wonder others emerge.

This brings me back to the original thread where I offered to read my code as it is more detailed than the wiki and easier to digest than the Satoshi code. People read my code likely recognize that there is quite a work in there and that it was written with modularity in mind, so they do not create yet an other script engine for their project, not because I FUD, but because it is welcoming and I do seek to resolve any incompatibility I find myself, with existing test cases, or if I am told an issue.

Happy New Year to you!

[smtp]

If operands are not available for an operator, that means the script is invalid.

So I guess it is THE classical stack-concept and script evaluation always starts with an empty (later always of finite depth) stack.

Better not assume anything. For certainty, read the Satoshi code.

You must assume if you have not complete information but wanted to act reasonably.
Could you give me a reference for this what you call "Satoshi code" - at best with a public available URL? I googled already but got only 634 hits and the most promising URL https://bitcointalk.org/index.php?topic=91004.0 I can't understand.

Anything that doesn't meet the expectations of the OP-code results in an invalid script.

Okay, this matches grau's statement (assumping that it is evident what all the expectations of a specific Op-code are!).

If it checks a signature using the top stack item as a public key, but the stack data does not parse as a public key, return SCRIPT_INVALID

Who does the parsing? I hope not me explicitly, but a (selectable) library function which depends on the run-time environment. :-/
Currently the only nontrivial library I use is the openssl library (libssl3.so.12) for SHA256 and RIPEMD160 hashing, but these functions I could also code to be independent of these library-versions - if I like.

If there are no more opcodes to run and the top stack item is not OP_TRUE, return SCRIPT_INVALID (I think I remember that's how it works...been a while...)

This contradicts the URL https://en.bitcoin.it/wiki/Script where is stated in the beginning of the article:

A transaction is valid if nothing in the combined script triggers failure and the top stack item is true (non-zero).

. So what is correct -- if you remember correctly?

Code:

       # Gavin clarified the effects of OP_0, and OP_1-OP_16.
      #       OP_0 puts an empty string onto the stack, which evaluates to
      #            false and is treated by HASH160 as '' (length=zero)
      #       OP_X puts a single byte onto the stack, 0x01 to 0x10

To be frank, I see here no subtilities. OP_X stands for the range of OP_1 up to OP_16, each pushing 1 byte onto the stack. OP_O in contrast like the whole range of nemonics with the byte values 0 - 75 each pushs 1 item onto the stack , a byte vector of length of its opcode.  This sounds to me like independent kind to push data onto the stack (like Op-codes with byte values 76 - 78 a further different kind). Anyway, at least I think I have interpreted the same meaning from the URL https://en.bitcoin.it/wiki/Script like you.
Appendum: Hm .... the ugly "subtility" (I would call it an ugly design decision) is that the op-code value 0x50 is a reserved op-code and not the op-code for pushing the byte 0 onto the stack. Maybe one better should have called the nemonic OP_0 OP_Empty to avoid misinterpretation or give it no official nemonic like all the op-codes with byte values <= 75?

I dislike to comment or even ask anymore to the replies given, in spite there have been arosen many questions by the following reply-postings from grau & gmaxwell. My feeling is: I have hiten a wasp's nest which is due to the fact, that there exist no (complete) definition of this scripting language only a historic implementation which is used as a reference (including all its bugs, subtilities, environment depending stuff, etc.) It would be nice if I'm wrong.

Maybe the "community" has to wait until serious commercial interests takes place on bitcoin (if anytime) and then surely forks in bitcoin-client script interpretation will result which are incompatible resulting in a mess and much worry -- perhaps the end or the unimportance of the known bitcoin-network.

In the blockchain there appear a few certain deposit-scripts:  0x73 0x63 0x72 0x69 0x70 0x74 (nemonics as OP_IFDUP OP_IF OP_2SWAP OP_VERIFY OP_2OVER OP_DEPTH) which were not redeemed. I wondered about this crazy script, but it triggered the question: if an OP_IF (or OP_NOTIF) is not closed by an OP_ENDIF inside a script, is the whole script then surely invalid or is this not necessarily invalid?

Thanks all for your informations and help
smtp

[etotheipi]

If there are no more opcodes to run and the top stack item is not OP_TRUE, return SCRIPT_INVALID (I think I remember that's how it works...been a while...)

This contradicts the URL https://en.bitcoin.it/wiki/Script where is stated in the beginning of the article:

A transaction is valid if nothing in the combined script triggers failure and the top stack item is true (non-zero).

. So what is correct -- if you remember correctly?

I'm not sure why you think that's contradictory? The only difference between the two statements is that I said it must be OP_TRUE, the page says non-zero.  Otherwise, they are the same statement.  You can't get to "no more OP-codes on the stack" without the first condition stated by that page, "nothing in the combined script triggers failure". 

Code:

      # Gavin clarified the effects of OP_0, and OP_1-OP_16.
      #       OP_0 puts an empty string onto the stack, which evaluates to
      #            false and is treated by HASH160 as '' (length=zero)
      #       OP_X puts a single byte onto the stack, 0x01 to 0x10

To be frank, I see here no subtilities. OP_X stands for the range of OP_1 up to OP_16, each pushing 1 byte onto the stack. OP_O in contrast like the whole range of nemonics with the byte values 0 - 75 each pushs 1 item onto the stack , a byte vector of length of its opcode.  This sounds to me like independent kind to push data onto the stack (like OP_codes with byte values 76 - 78 a further different kind). Anyway, at least I think I have interpreted the same meaning from the URL https://en.bitcoin.it/wiki/Script like you.

This is not necessarily intuitive, at least not from the naming.  I spent many hours putting a single zero-byte onto the stack and trying to figure out why my script eval was failing certain OP_CHECKMULTISIG scripts.  It's because OP_HASH160 obviously gives a different answer for "" (empty-string) than it does a single zero-byte.  I see the page now says "put an empty string onto the stack" for OP_0 -- I'm pretty sure that was added after I complained to Gavin about how that is a rather important detail that wasn't documented.  My only point was that there are lots of tiny details and they are likely not to be documented well.  So, have fun

[smtp]

Hi

I'm not sure why you think that's contradictory? The only difference between the two statements is that I said it must be OP_TRUE, the page says non-zero.  Otherwise, they are the same statement.

OP_TRUE is identical to the byte with byte value 0x01 = decimal value 1. Your interpretation sounds as if there is a unique "true" value, this one byte value.
On the other hand, "true (non-zero)" means every stack-item which value is not 0 is interpreted as true. So if the final top-stack item is, say,  47 this would also be interpretated as true as well as the byte vector of length 3 "0x01 0x00 0x00" which is also not identical to OP_TRUE (but has the same value 1).

This is not necessarily intuitive, at least not from the naming.  I spent many hours putting a single zero-byte onto the stack and trying to figure out why my script eval was failing certain OP_CHECKMULTISIG scripts.  It's because OP_HASH160 obviously gives a different answer for "" (empty-string) than it does a single zero-byte.  I see the page now says "put an empty string onto the stack" for OP_0 -- I'm pretty sure that was added after I complained to Gavin about how that is a rather important detail that wasn't documented.  My only point was that there are lots of tiny details and they are likely not to be documented well.

I see. Meanwhile I had added a Appendum to this minor point, which indeed critize the naming of the nemonic OP_0.

So, have fun

Thx,
smpt

[etotheipi]

Hi

I'm not sure why you think that's contradictory? The only difference between the two statements is that I said it must be OP_TRUE, the page says non-zero.  Otherwise, they are the same statement.

OP_TRUE is identical to the byte with byte value 0x01 = decimal value 1. Your interpretation sounds as if there is a unique "true" value, this one byte value.
On the other hand, "true (non-zero)" means every stack-item which value is not 0 is interpreted as true. So if the final top-stack item is, say,  47 this would also be interpretated as true as well as the byte vector of length 3 "0x01 0x00 0x00" which is also not identical to OP_TRUE (but has the same value 1).

I wasn't trying to give you rigorous implementation details.  You asked a very general question in the top post, so I was giving very general description about how things work.  It wasn't intended to be precise, as nothing that could be written here would be.  You'll have to go to the reference code for that.

[smtp]

In the blockchain there appear a few certain deposit-scripts:  0x73 0x63 0x72 0x69 0x70 0x74 (nemonics as OP_IFDUP OP_IF OP_2SWAP OP_VERIFY OP_2OVER OP_DEPTH) which were not redeemed. I wondered about this crazy script, but it triggered the question: if an OP_IF (or OP_NOTIF) is not closed by an OP_ENDIF inside a script, is the whole script then surely invalid or is this not necessarily invalid?

It is invalid (at least since bitcoinclient version 0.3.23).

This answer (and many other insights) I got by carefully studying the file src/src/script.cpp of the bitcoinclient-0.7.1 distribution. Meanwhile I used my information to update, correct and make more complete the wiki-page https://en.bitcoin.it/wiki/Script for other newbies.

smtp

[Gavin Andresen]

In the blockchain there appear a few certain deposit-scripts:  0x73 0x63 0x72 0x69 0x70 0x74 (nemonics as OP_IFDUP OP_IF OP_2SWAP OP_VERIFY OP_2OVER OP_DEPTH)

That is ascii for 'script' -- and was an unfortunate bug in somebody's software, if I recall correctly.

I used my information to update, correct and make more complete the wiki-page https://en.bitcoin.it/wiki/Script for other newbies.

Excellent! The first step to bitcoin development enlightenment is realizing that you are a part of the process...