Tons of non-standard scripts!

[etotheipi]

I went on a scavenger hunt, looking for non-std scripts I could use to test my script evaluation engine.  Unfortunately (?), the main-network is rather boring in this sense, but the testnet has quite a few goodies.  I put a complete dump of every non-std script from the testnet onto github/gist:

All non-std scripts in a text-file on gist!

Now onto my questions:

• (1) What is going on with the first half-dozen Coinbase-TxOut scripts that would normally just be a public-key?  There's the normal 0x04 byte at the beginning (as if it were a public key), and OP_CHECKSIG at the end, but then there's 70 bytes of data between them, instead of the usual 64.  The following 6 bytes are what follows the 0x04:   "00 a0 34 20 00 44".  In my code, I push all 71 bytes onto the stack, but my code doesn't recognize it as a public key.  In fact, I've tried looking at consecutive 32/32 bytes chunks but none of them correspond to a point on the secp256k1 curve.  (None of them have been spent, so I suppose these could be unspendable TxOut scripts)
• (2) I attained these by examining the blockchain file created by the 0.4.0 client when run in testnet mode.  Then, is it correct to assume that all these scripts are actually valid, and my code should be able to evaluate all of them to true?  I am under the impression that the satoshi client does all verification checks on every block/tx that is received, and thus invalid scripts wouldn't make it into blk0001.dat. 
• (3) I am aware that there is a bug with OP_CHECKMULTISIG that causes it to pop too many elements off the stack.  It sounds like we're working our way around that bug in the upcoming multi-sig tx isStandard.   Are there any other anomalies in the scripting engine that I should know about?  It sounds like the satoshi-client behavior is "truth" and thus I should match it, even if it doesn't quite match the intended design.

Just for fun, here's two exciting scripts from the testnet -- the first is a TxOut, the second is the TxIn that spends the TxOut:

TxOut Script:

Code:

   3
   OP_ROLL
   OP_DUP
   2
   OP_GREATERTHANOREQUAL
   OP_VERIFY
   3
   OP_ROLL
   OP_SIZE
   OP_NOT
   OP_OVER
   OP_HASH160
   [PUSHDATA -- 20 BYTES:]
   80677c5392220db736455533477d0bc2fba65502
   OP_EQUAL
   OP_BOOLOR
   OP_VERIFY
   3
   OP_ROLL
   OP_SIZE
   OP_NOT
   OP_OVER
   OP_HASH160
   [PUSHDATA -- 20 BYTES:]
   02d7aa2e76d9066fb2b3c41ff8839a5c81bdca19
   OP_EQUAL
   OP_BOOLOR
   OP_VERIFY
   3
   OP_ROLL
   OP_SIZE
   OP_NOT
   OP_OVER
   OP_HASH160
   [PUSHDATA -- 20 BYTES:]
   10039ce4fdb5d4ee56148fe3935b9bfbbe4ecc89
   OP_EQUAL
   OP_BOOLOR
   OP_VERIFY
   3
   OP_CHECKMULTISIG

TxIn Script:

Code:

   OP_0
   [PUSHDATA -- 73 BYTES:]
   3046022100d73f633f114e0e0b324d87d38d34f22966a03b072803afa99c9408201f6d6dc6022100900e85be52ad2278d24e7edbb7269367f5f2d6f1bd338d017ca460008776614401
   [PUSHDATA -- 71 BYTES:]
   3044022071fef8ac0aa6318817dbd242bf51fb5b75be312aa31ecb44a0afe7b49fcf840302204c223179a383bb6fcb80312ac66e473345065f7d9136f9662d867acf96c12a4201
   2
   [PUSHDATA -- 65 BYTES:]
   048c006ff0d2cfde86455086af5a25b88c2b81858aab67f6a3132c885a2cb9ec38e700576fd46c7d72d7d22555eee3a14e2876c643cd70b1b0a77fbf46e62331ac
   [PUSHDATA -- 65 BYTES:]
   04b68ef7d8f24d45e1771101e269c0aacf8d3ed7ebe12b65521712bba768ef53e1e84fff3afbee360acea0d1f461c013557f71d426ac17a293c5eebf06e468253e
   OP_0

[1714044200]

1714044200

[1714044200]

1714044200

[Gavin Andresen]

1. TxOut scripts are not evaluated until they are spent-- those are probably unspendable TxOuts.

2. The inputs must be valid (you're looking at coinbase txns with no inputs though). Again, TxOuts aren't evaluated until they are used as inputs in another transaction; as long as they deserialize properly they'll be accepted.

3. I don't know of any other bugs in the scripts ops, but I don't know that anybody has written thorough unit tests for them (anybody looking for a good get-your-feet-wet project that could be a good one to tackle; there are already unit tests for CHECKMULTISIG in the repostitory....).

[etotheipi]

1. TxOut scripts are not evaluated until they are spent-- those are probably unspendable TxOuts.

Fair enough... I was wondering if there was a reason to believe they were spendable, and thus I need to add something to my scripting code to accommodate.  I'm really just looking for a sanity check.  It sounds like there's no action here.. at least not until someone demonstrates they are spendable and my code would've failed.

2. The inputs must be valid (you're looking at coinbase txns with no inputs though). Again, TxOuts aren't evaluated until they are used as inputs in another transaction; as long as they deserialize properly they'll be accepted.

Looking back, I see that the transactions are coinbase, but the non-std scripts are in the TxOuts -- which means they could've been put on any transaction, not specific to coinbase.  So my response is the same here as in #1 -- I'll just assume they are unspendable and that I don't need to accommodate anything new in script engine.  You make a good point that TxOut scripts can be anything, so I'll just always assume they are unspendable until I see evidence otherwise.

3. I don't know of any other bugs in the scripts ops, but I don't know that anybody has written thorough unit tests for them (anybody looking for a good get-your-feet-wet project that could be a good one to tackle; there are already unit tests for CHECKMULTISIG in the repostitory....).

It sounds like that arbitrary scripts have been run through the client software successfully in the past (such as these testnet scripts), but there hasn't been any rigorous efforts to check that it's robust, etc.  I would volunteer, but I'm not sure how to isolate the ref client scripting engine, and then still throw in things like OP_CHECKSIG evaluations which require more than just the script itself (such as the whole Tx and the ECDSA verification methods).

[Gavin Andresen]

It sounds like that arbitrary scripts have been run through the client software successfully in the past (such as these testnet scripts), but there hasn't been any rigorous efforts to check that it's robust, etc.  I would volunteer, but I'm not sure how to isolate the ref client scripting engine, and then still throw in things like OP_CHECKSIG evaluations which require more than just the script itself (such as the whole Tx and the ECDSA verification methods).

See src/test/script_test.cpp in git HEAD.
Or for more examples of testing script operations, the unit tests I wrote here:
  https://github.com/gavinandresen/bitcoin-git/blob/op_eval/src/test/script_op_eval_tests.cpp
  https://github.com/gavinandresen/bitcoin-git/blob/op_eval/src/test/multisig_tests.cpp

[nibor]

some are mine... see:
https://bitcointalk.org/index.php?topic=43821.msg529672#msg529672

Input non-std transaction:
http://blockexplorer.com/testnet/t/6ttfeb55B1

Spent by:
http://blockexplorer.com/testnet/t/AFdRB1CHS3


They just insert some text ("bob" in hex I think, then drop it).
They are however spendable.

At the time I was trying to think of a way you could spend some outputs without Block Explorer realising. As that would be dangerous as I am sure a lot of people put too much faith in Block Explorer always being correct (which it is  !).

But since BE can just look to see if there is a valid transaction that has spent this output it is very hard to fool it.

[etotheipi]

Okay, I am now battling the OP_CHECKMULTISIG example in my original post.  I thought the point of OP_CHECKMULTISIG was to be simple and not require two-dozen other op-codes to get an M-of-N transaction.  It seems to me that it is simple if you have everyone's public key, but not if you have their address.  Is this really the simplest way to do M-of-N with 3 addresses? (see top post)

Second of all, I'm a little confused about the script itself.  I am crashing when I try to HASH160 an OP_0 byte, but I can't figure out what my scripting code did wrong.  Perhaps someone with scripting experience can point me to my error.  This is the exact state of my stack after every OP_CODE:

Code:

TxIn Script:
   OP_0:      0
   OP_PUSH:   0   SigA
   OP_PUSH:   0   SigA   SigB
   OP_2:      0   SigA   SigB   2
   OP_PUSH:   0   SigA   SigB   2   PubKeyA
   OP_PUSH:   0   SigA   SigB   2   PubKeyA   PubKeyB
   OP_0:      0   SigA   SigB   2   PubKeyA   PubKeyB   0

TxOut Script (with stack from TxIn):
   OP_3:      0   SigA   SigB   2   PubKeyA   PubKeyB   0   3
   OP_ROLL:   0   SigA   SigB   PubKeyA   PubKeyB   0   2
   OP_DUP:    0   SigA   SigB   PubKeyA   PubKeyB   0   2   2
   OP_2:      0   SigA   SigB   PubKeyA   PubKeyB   0   2   2   2
   OP_>=:     0   SigA   SigB   PubKeyA   PubKeyB   0   2   1
   OP_VERIFY: 0   SigA   SigB   PubKeyA   PubKeyB   0   2
   OP_3:      0   SigA   SigB   PubKeyA   PubKeyB   0   2   3
   OP_ROLL:   0   SigA   SigB   PubKeyB   0   2   PubKeyA
   OP_SIZE:   0   SigA   SigB   PubKeyB   0   2   PubKeyA   65
   OP_NOT:    0   SigA   SigB   PubKeyB   0   2   PubKeyA   0
   OP_OVER:   0   SigA   SigB   PubKeyB   0   2   PubKeyA   0   PubKeyA
   OP_HASH:   0   SigA   SigB   PubKeyB   0   2   PubKeyA   0   PubAHash
   OP_PUSH:   0   SigA   SigB   PubKeyB   0   2   PubKeyA   0   PubAHash   PubAHash
   OP_EQUAL:  0   SigA   SigB   PubKeyB   0   2   PubKeyA   0   1
   OP_BOOLOR: 0   SigA   SigB   PubKeyB   0   2   PubKeyA   1
   OP_VERIFY: 0   SigA   SigB   PubKeyB   0   2   PubKeyA
   OP_3:      0   SigA   SigB   PubKeyB   0   2   PubKeyA   3
   OP_ROLL:   0   SigA   SigB   0   2   PubKeyA   PubKeyB
   OP_SIZE:   0   SigA   SigB   0   2   PubKeyA   PubKeyB   65
   OP_NOT:    0   SigA   SigB   0   2   PubKeyA   PubKeyB   0
   OP_OVER:   0   SigA   SigB   0   2   PubKeyA   PubKeyB   0   PubKeyB
   OP_HASH:   0   SigA   SigB   0   2   PubKeyA   PubKeyB   0   PubBHash
   OP_PUSH:   0   SigA   SigB   0   2   PubKeyA   PubKeyB   0   PubBHash   PubBHash
   OP_EQUAL:  0   SigA   SigB   0   2   PubKeyA   PubKeyB   0   1
   OP_BOOLOR: 0   SigA   SigB   0   2   PubKeyA   PubKeyB   1
   OP_VERIFY: 0   SigA   SigB   0   2   PubKeyA   PubKeyB
   OP_3:      0   SigA   SigB   0   2   PubKeyA   PubKeyB   3
   OP_ROLL:   0   SigA   SigB   2   PubKeyA   PubKeyB   0
   OP_SIZE:   0   SigA   SigB   2   PubKeyA   PubKeyB   0   1
   OP_NOT:    0   SigA   SigB   2   PubKeyA   PubKeyB   0   0
   OP_OVER:   0   SigA   SigB   2   PubKeyA   PubKeyB   0   0   0
   OP_HASH160:  <ERROR>

Can anyone help identify what op-code I mis-applied?  These two scripts are straight from the testnet, and the 0.4.0 client accepted them as a valid pair.

[ByteCoin]

I am crashing when I try to HASH160 an OP_0 byte, but I can't figure out what my scripting code did wrong.

I believe that "crashing when you try to HASH160 an OP_0 byte" is what your scripting code did wrong.

ByteCoin

[etotheipi]

I am crashing when I try to HASH160 an OP_0 byte, but I can't figure out what my scripting code did wrong.

I believe that "crashing when you try to HASH160 an OP_0 byte" is what your scripting code did wrong.

ByteCoin

Gah!  That was stupid. 

I assumed that HASH160 should only ever operate on strings, and thus I must've done something wrong upstream to end up with a HASH160(OP_0).  Upon closer inspection, I see that zero is actually a placeholder for the third public key that wasn't supplied.  I just need to "define" HASH160(OP_0) to return...anything.

That's what I get for making assumptions...
Thanks.

[Gavin Andresen]

OP_0 pushes an empty array of bytes onto the stack, so you should RIPEMD160(SHA256([])).

(thanks go genjix for setting me straight, I'd been thinking OP_0 pushed a 0x00 onto the stack, and that isn't right.  The scripting engine knows that an empty array is 'False', and FIPS standards make sure hashing empty strings/arrays is well-defined...)

[etotheipi]

Most interesting.  If I wasn't about to board a plane right now, I'd go clarify that on the Bitcoin Scripting wiki...

Do all OP_X codes push an empty string onto the stack?   Or just OP_0?  Is it safe to assume that it is an error if I somehow end up with HASH160(OP_3)?

[Gavin Andresen]

OP_1 through OP_16 push single bytes (0x01 through 0x10) onto the stack.

RE: updating the wiki:  good idea, I'll go do that...