Did the introduction of VerifyScript cause a backwards incompatible change to consensus?

Question

My question is about the changes to bitcoin done by commit range [a75560d8, 6ff5f718], and their effect on consensus. Out of this range of four commits (all attributed to satoshi) during the dates July 30th-31st 2010, only the first and last commits are relevant to the question (the two in the middle seem like a build system change, not code).

The two commits (first and second from now on), a75560d8 and 6ff5f718 are attributed to fixing quite a few vulnerabilities in bitcoin script semantics and execution. For example, in the first commit :

1. Constraints were applied to push and stack sizes
2. The so-called script versioning mechanism was removed, and the various NOP# opcodes were added in its place
3. Constraints were applied to bignum operations
4. OP_RETURN was changed from merely terminating the script to returning false for the entire execution

In the second commit :

1. Constraints were applied on the maximum number of opcodes in the script
2. Execution of unknown opcodes was set to return false for the execution
3. The maximum size of the script was reduced by half to 10kb
4. A change to *SHIFT opcodes was done (I don't really uderstand it though)
5. A function called VerifyScript was introduced into bitcoin which changed the behavior of script execution

This question is about this list of changes, and whether any of them might be non backwards compatible. Specifically, I will focus on change (5) from the second commit : 6ff5f718:script.cpp

Before this change, at the point of txout redemption, a redeeming transaction's input's scriptSig and the prevout's scriptPubKey were joined to form a single script by placing an OP_CODESEPARATOR between them, and passing the result to EvalScript which would execute the script.

Inside EvalScript, an empty stack was created and results from the various operations done in the script are pushed onto it. When script execution completes without errors, a boolean is returned; if the stack is not empty then the top element is passed to a CastToBool function and and returned (true or false), and if the stack is empty then false is returned.

After the change, the VerifyScript function wraps around two separate calls to EvalScript, executing scriptSig and scriptPubKey separately one after the other. The empty stack which was previously created within EvalScript is instead created in VerifyScript before any script execution begins, and the final check of the stack's contents (or lack thereof) and CastToBool was also moved to VerifyScript, to the point after both scriptSig and scriptPubKey completed their execution.

In VerifyScript, first the scriptSig from the redeeming transaction is passed to EvalScript along with the empty stack. The machine executes the script and results from the operations are pushed to the stack that was passed in with it. If no errors occurred during execution, true is returned to VerifyScript. Secondly, if indeed true was returned, the scriptPubKey from the funding transaction is passed to EvalScript along with the stack, which at that point holds the contents left over from scriptSig's execution. The scriptPubKey is executed, which further manipulates the stack's contents and if no errors occured, returns true back to VerifyScript. Lastly, if true was returned, then the check for empty stack and CastToBool are done, which determines the final result of script verification.

The reason for this change was cited as being a fix to a possible vulnerability in Script : SE answer, BCTalk thread. Although it's orthogonal to this question, it's why I included the list of changes from commit a75560d8.

It's not too hard to see that considering simple (lacking a checksig) scripts, this change is indeed backwards compatible. At worst, some scripts might become unspendable, but there doesn't seem to be a case where a previously unspendable script might become spendable as a result of this change.

Even for scripts with a checksig like p2pk, p2pkh and multisig, the CHECKSIG opcode is always taking place in scriptPubKey, which was separated from the elements of scriptSig by an OP_CODESEPARATOR prior to this change. Seemingly, the semantics remained the same - until about two years later.

Looking at the wiki page for OP_CHECKSIG wiki-checksig, steps (2) to (4) explain how to go from scriptCode to subScript, and specifically what happens when an OP_CODESEPARATOR exists in scriptCode :

2. A new subScript is created from the scriptCode (the scriptCode is the actually executed script - either the scriptPubKey for non-segwit, non-P2SH scripts, or the redeemscript in non-segwit P2SH scripts). The script from the immediately after the most recently parsed OP_CODESEPARATOR to the end of the script is the subScript. If there is no OP_CODESEPARATOR the entire script becomes the subScript
3. Any occurrences of sig are deleted from subScript, if present (it is not standard to have a signature in an input script of a transaction)
4. Any remaining OP_CODESEPARATORS are removed from subScript

Now, prior to commit 6ff5f718, when scriptSig and scriptPubKey were joined to form a single script, the scriptCode would look like :

<scriptSig> CODESEPARATOR <scriptPubKey>

With checksig operations taking place in scriptPubKey, making subScript be everything to the right of CODESEPARATOR - basically <scriptPubKey> itself (unless more codeseparators or if signatures consumed by a checksig also exist in scriptPubKey).

After the commit, there would actually be two separate executions with scriptSig first and scriptPubKey second, where each execution would have its own scriptCode and subsequently its own subScript. Now, Because checksig operations are still only being done in scriptPubKey, it appears that subScript would remain the same, but what would happen if a CHECK(MULTI)SIG opcode gets executed in scriptSig?

In January 24th 2012, block 163685 was mined which contained transaction eb3b82c0884e3efa6d8b0be55b4915eb20be124c9766245bcc7f34fdac32bccb. This transaction, the two immediately after it, and its funding at b8fd633e7713a43d5ac87266adc78444669b987a56b3a65fb92d58c2c4b0e84d which were also mined in the same block are all mentioned in BIP-17, which is an alternative implementation of p2sh semantics :

• OP_CHECKHASHVERIFY will re-define the existing OP_NOP2 opcode, and will function as follows when executed:

• First, hash the end of the prior script (in the general case, scriptSig; if no prior script, a null string is hashed) beginning from the last evaluated OP_CODESEPARATOR onward (or from the beginning of the script, if no OP_CODESEPARATOR was present)

• Then, compare this with the item on the top of the stack (if there is none, the script fails immediately)
• If the hashes match, do nothing, proceed as if an OP_NOP; if they do not match, the script fails immediately. Note that in the case of a matched hash, the top stack item (the hash being compared with) is not popped off the stack. This is for backward compatibility.

Notice how in bip17 the redeemScript is given as an actual executable script in scriptSig, rather than a single data push of a blob as is the case with bip16. Even though older nodes will not enforce the hash160 of scriptSig to be equal to the 20 bytes value from prevout's scriptPubKey, they would still have to execute it and validate any CHECK(MULTI)SIG operations within.

I'm assuming here that these bip17 example transactions were mined and validated by nodes running software that was recent in Jan. 2012, but suppose there were still nodes on the network running older software, and specifically ones running versions v0.3.6 and lower. Would these older nodes be able to come to consensus with the newer nodes about the validity of block 163685?

Going over the funding transaction b8fd633e7713a43d5ac87266adc78444669b987a56b3a65fb92d58c2c4b0e84d, and looking at the output at index 1, we see the scriptPubKey (NOP2 is actually a non active OP_CHECKHASHVERIFY)

0x14 0x2a9bc5447d664c1d0141392a842d23dba45c4f13 NOP2 DROP

And in the spending transaction eb3b82c0884e3efa6d8b0be55b4915eb20be124c9766245bcc7f34fdac32bccb, from the input at index 1, we have the scriptSig

0 0x47 0x30440220276d6dad3defa37b5f81add3992d510d2f44a317fd85e04f93a1e2daea64660202200f862a0da684249322ceb8ed842fb8c859c0cb94c81e1c5308b4868157a428ee01 CODESEPARATOR 1 0x21 0x0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a 1 CHECKMULTISIG

Consider first how software from v0.3.7 and above would construct the subScript for the CHECKMULTISIG in scriptSig. We begin with a scriptCode which is exactly scriptSig, and since a CODESEPARATOR is executed, subScript becomes :

1 0x21 0x0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a 1 CHECKMULTISIG

Now consider how software from v0.3.6 and below would construct the subScript for the same CHECKMULTISIG. Our scriptCode is no longer made from only scriptSig, but from a joining of it and scriptPubKey by a CODESEPARATOR. The scriptCode would look like :

0 0x47 0x30440220276d6dad3defa37b5f81add3992d510d2f44a317fd85e04f93a1e2daea64660202200f862a0da684249322ceb8ed842fb8c859c0cb94c81e1c5308b4868157a428ee01 CODESEPARATOR 1 0x21 0x0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a 1 CHECKMULTISIG CODESEPARATOR 0x14 0x2a9bc5447d664c1d0141392a842d23dba45c4f13 NOP2 DROP

Recall the rules from the wiki. At the point when CHECKMULTISIG is executed, subScript is everything from the point after the last executed CODESEPARATOR and until the end of the script, with all CODESEPARATORs on the right hand side of the checksig operator removed :

1 0x21 0x0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a 1 CHECKMULTISIG 0x14 0x2a9bc5447d664c1d0141392a842d23dba45c4f13 NOP2 DROP

If this is correct, then it appears that old nodes with versions v0.3.6 and below cannot agree on which is the correct sighash for this spending transaction, but since I can't realistically run any such old version software, I can't be absolutely sure. I did patch a recent bitcoin core version with some changes that enabled me to simulate validation of tx eb3b82c0884e3efa6d8b0be55b4915eb20be124c9766245bcc7f34fdac32bccb, and as expected it did not pass validation. I will add the two sighashes below along with the public key and signature for comparison.

So my question is, is there something I'm misunderstanding or perhaps missed that would allow pre-v0.3.7 and post-v0.3.7 nodes to come to consensus about the validity of block 163685?

(also relevant : this SE question)

---

Pubkey : 0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a
Signature (DER) : 30440220276d6dad3defa37b5f81add3992d510d2f44a317fd85e04f93a1e2daea64660202200f862a0da684249322ceb8ed842fb8c859c0cb94c81e1c5308b4868157a428ee
Signature (r,s) : (276D6DAD3DEFA37B5F81ADD3992D510D2F44A317FD85E04F93A1E2DAEA646602, F862A0DA684249322CEB8ED842FB8C859C0CB94C81E1C5308B4868157A428EE)

Pre-v0.3.7 sighash (does not validate) :

01000000
02
4de8b0c4c2582db95fa6b3567a989b664484c7ad6672c85a3da413773e63fdb8 00000000
00
FFFFFFFF
4de8b0c4c2582db95fa6b3567a989b664484c7ad6672c85a3da413773e63fdb8 01000000
3C 51210232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a51ae142a9bc5447d664c1d0141392a842d23dba45c4f13b175
FFFFFFFF
02
E0FD1C0000000000 19 76a914380cb3c594de4e7e9b8e18db182987bebb5a4f7088ac
C0C62D0000000000 17 142a9bc5447d664c1d0141392a842d23dba45c4f13b175
00000000
01000000

sha256  : 1EB276326D72CB358F6C275D6542F76EED4E36364727CB82D40A116244EBDDB5
sha256d : 11491E74778E1FA8C40CC8E07E1F835677CF1AC81F54255EC1C7125C1894939A

Post-v0.3.7 sighash (does validate) :

01000000
02
4de8b0c4c2582db95fa6b3567a989b664484c7ad6672c85a3da413773e63fdb8 00000000
00
FFFFFFFF
4de8b0c4c2582db95fa6b3567a989b664484c7ad6672c85a3da413773e63fdb8 01000000
25 51210232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a51ae
FFFFFFFF
02
E0FD1C0000000000 19 76a914380cb3c594de4e7e9b8e18db182987bebb5a4f7088ac
C0C62D0000000000 17 142a9bc5447d664c1d0141392a842d23dba45c4f13b175
00000000
01000000

sha256  : 3858A592C15A47F3058010689883DECCD4AF41F5367B9776429613DFB3339883
sha256d : 8D7AD159644D312664472F90E7B823071B1361725CAC78531569FD836EA90350

Answer 1

Almost all commits to the client prior to the commits that you have called out here were hard forks to due the inclusion of OP_VER and OP_VERIF, even if the change to the client wasn't otherwise an incompatible change.

        case OP_VER:
        {
            CBigNum bn(VERSION);
            stack.push_back(bn.getvch());
        }
        break;

Quite simply, the opcode pushes VERSION onto the stack, which is the version number of the code being used to validate. This number was updated with every release, so no two versions prior to its removal are actually compatible with one another.

There's several others which you have not mentioned, such as that nLockTime was changed to an unsigned variable with a height based hard fork, some minor changes to the implementations of the opcodes, and the removal of double byte opcodes. It's very difficult to enumerate which of these versions are actually compatible with each other as a result of the huge number of changes, and the poor tooling we have which is compatible with these ancient versions.