How is subscript computed for OP_CHECKMULTISIG?

Question

I'm trying to learn the Bitcoin protocol by implementing it, and I've got OP_CHECKSIG working (following instructions in https://en.bitcoin.it/wiki/OP_CHECKSIG), but I can't get an transaction input using OP_CHECKMULTISIG to pass signature verification.

Specifically, I'm stuck with the second tx_input of transaction eb3b82c0884e3efa6d8b0be55b4915eb20be124c9766245bcc7f34fdac32bccb, and I suspect that the culprit is subscript (the one to replace signature script in current transaction).

Here's how subscript is computed in my implementation.

First, generate the script by concatenating [sigScript][OP_CODESEPARATOR][pubkeyScript] (I understand that script execution has evolved from this).

So a (parsed) script for the input would be like this:

Frame 00: 0(00) Frame 01: 0000 - 30 44 02 20 27 6d 6d ad 3d ef a3 7b 5f 81 ad d3 0010 - 99 2d 51 0d 2f 44 a3 17 fd 85 e0 4f 93 a1 e2 da 0020 - ea 64 66 02 02 20 0f 86 2a 0d a6 84 24 93 22 ce 0030 - b8 ed 84 2f b8 c8 59 c0 cb 94 c8 1e 1c 53 08 b4 0040 - 86 81 57 a4 28 ee 01 END Frame 02: OP_CODESEPARATOR(0xab) Frame 03: 1(0x51) Frame 04: 0000 - 02 32 ab dc 89 3e 7f 06 31 36 4d 7f d0 1c b3 3d 0010 - 24 da 45 32 9a 00 35 7b 3a 78 86 21 1a b4 14 d5 0020 - 5a END Frame 05: 1(0x51) Frame 06: OP_CHECKMULTISIG(0xae) Frame 07: OP_CODESEPARATOR(0xab) Frame 08: 0000 - 2a 9b c5 44 7d 66 4c 1d 01 41 39 2a 84 2d 23 db 0010 - a4 5c 4f 13 END Frame 09: OP_NOP2/OP_CHECKLOCKTIMEVERIFY(0xb1) Frame 10: OP_DROP(0x75)

Then, I create the subscript from the closest OP_CODESEPARATOR before the OP_CHECKMULTISIG that I am executing till the end of the script. So, I include Frame 03 to Frame 10.

Then, I remove other OP_CODESEPARATORs in the script, which is Frame 07.

That means these frames should compose the subscript:

Frame 03: 1(0x51) Frame 04: 0000 - 02 32 ab dc 89 3e 7f 06 31 36 4d 7f d0 1c b3 3d 0010 - 24 da 45 32 9a 00 35 7b 3a 78 86 21 1a b4 14 d5 0020 - 5a END Frame 05: 1(0x51) Frame 06: OP_CHECKMULTISIG(0xae) Frame 08: 0000 - 2a 9b c5 44 7d 66 4c 1d 01 41 39 2a 84 2d 23 db 0010 - a4 5c 4f 13 END Frame 09: OP_NOP2/OP_CHECKLOCKTIMEVERIFY(0xb1) Frame 10: OP_DROP(0x75)

Serialized, the final subscript looks like this:

0000 - 51 21 02 32 ab dc 89 3e 7f 06 31 36 4d 7f d0 1c 0010 - b3 3d 24 da 45 32 9a 00 35 7b 3a 78 86 21 1a b4 0020 - 14 d5 5a 51 ae 14 2a 9b c5 44 7d 66 4c 1d 01 41 0030 - 39 2a 84 2d 23 db a4 5c 4f 13 b1 75

However, when this subscript is used to replace signature script, and eventually generate hash, the ecdsa_verify function reports that signature verification fails (but the inputs are legal).

Since the same procedure works for OP_CHECKSIG, I probably missed something obvious, but I couldn't figure this out reading the original Satoshi code, the current implementation, or Bitcoin Wiki.

If it helps, my code for OP_CHECKMULTISIG is here: https://github.com/blaesus/tinybtc/blob/checkmultisig/src/script.c#L687

A more simplistic version (using prevTx.pubkeyScript as subscript) doesn't yield valid results either: https://github.com/blaesus/tinybtc/blob/validate/src/script.c#L344

Answer 1

The main confusion here comes from this :

First, generate the script by concatenating [sigScript][OP_CODESEPARATOR][pubkeyScript]

Then you add :

I understand that script execution has evolved from this

I'm not sure whether you mean "Builds upon this method" or "Has since changed this method", but if it is the former then this might explain the unexpected results that you're getting. Hopefully my answer can clear this up.

It's true that for a (relatively) short period Bitcoin's script evaluation was done by the way you mentioned, where a CODESEPARATOR was placed between scriptSig and scriptPubkey then the whole thing was concatenated to form a single script which would be executed, but that was changed rather early on in commit 6ff5f718b6a67797b2b3bab8905d607ad216ee21 which dates to July 31st 2010.

After said change, which introduced a function named VerifyScript in script.cpp (today the logic is in interpreter.cpp), scriptSig and scriptPubkey are no longer concatenated with a CODESEPARATOR between them. Rather they are executed as two separate scripts one after the other, where the stack's contents carries from the first to the second.

The difference is subtle and doesn't really change the flow of standard redemptions, but becomes noticable when a CHECKSIG operation is done within the scriptSig.

Starting from the funding transaction

b8fd633e7713a43d5ac87266adc78444669b987a56b3a65fb92d58c2c4b0e84d

we see that the second output in it is a payment to the following scriptPubKey at index 1 :

14 2a9bc5447d664c1d0141392a842d23dba45c4f13
NOP2
DROP

OP_CLTV is not active yet, so the opcode 0xb1 is still NOP2.

Which is then redeemed by

eb3b82c0884e3efa6d8b0be55b4915eb20be124c9766245bcc7f34fdac32bccb

by the input at index 1 :

0
47
  30
  44
    02
    20 276d6dad3defa37b5f81add3992d510d2f44a317fd85e04f93a1e2daea646602
    02
    20 0f862a0da684249322ceb8ed842fb8c859c0cb94c81e1c5308b4868157a428ee
  01
CODESEPARATOR
1
21 0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a
1
CHECKMULTISIG

In the short period before commit 6ff5f718, the two scripts would be concated with a CODESEPARATOR placed between them to form the complete script, then execution will start. We start with an empty stack, and a pointer to the beginning of the script marking the start of what would be the signed scriptCode :

1. Push 0 onto the stack
2. Push the signature onto the stack
3. Execute CODESEPARATOR - mark this point in the script as the start of scriptCode (overwriting the previous value set at the beginning)
4. Push 1 onto the stack
5. Push the pubkey onto the stack
6. Push 1 onto the stack
7. Execute 1-of-1 CHECKMULTISIG

At this point, we need to construct the scriptCode to be signed. The rules are :

1. Take the subscript from the last executed CODESEPARATOR up until the end of the script
2. Remove all CODESEPARATORS
3. Remove all occurences of the signature that is currently being verified

Since the signature is actually before the last CODESEPARATOR, rule #3 doesn't come into effect here, but rules #1 and #2 do. This leaves us with the following scriptCode :

1
21 0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a
1
CHECKMULTISIG
14 2a9bc5447d664c1d0141392a842d23dba45c4f13
NOP2
DROP

Which is what you initially came up with, but now let's see how the change at 6ff5f718 makes a difference.

Recall that we are now dealing with two separate scripts, but none of the other rules change. The only difference is that these two scripts are executed separately, one after the other, and that the stack that remains from the execution of scriptSig passes on to the execution of scriptPubkey.

We start by executing scriptSig and go through steps #1 - #7 as before, arriving at the same point of CHECKMULTISIG where we construct the scriptCode. Since the actual executed script now consists of only what was in scriptSig, scriptCode becomes :

1
21 0232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a
1
CHECKMULTISIG

If this signature check passes (and it does), a value of 1 is pushed onto the stack, and scriptSig execution ends successfuly. This stack now passes on to the exectution of scriptPubkey (which is very simple) and eventually left as the final value on the stack, which makes scriptPubkey resolve to True.

This transaction is very interesting really shows how non-trivial commit 6ff5f718 actually was. It's a great example.

Another minor thing to note is that this scriptPubKey by itself is an anyone-can-spend script. This script's conditions are satisfiable simply by passing a single push of an element which evaluates to True (e.g. 1 - 0x51) and that the signature check in scriptSig actually has no significance and does not secure the funds at all.

Edit :

Actually, looking into this some more, it seems that this transaction is specifically mentioned in BIP-17 (which has since been abandoned). The 20 bytes in scriptPubkey is actually the hash160 of the 1-of-1 multisig script itself :

51210232abdc893e7f0631364d7fd01cb33d24da45329a00357b3a7886211ab414d55a51ae

This is in fact one of the example bip-17 transactions placed on chain by the bip's author. Should this bip had been accepted, such a transaction would not be anyone-can-spend. (you can see more details in the bip itself)

Answer 2

I figured it out myself (by trying all substrings of the script).

The correct subscript is this:

0000 - 51 21 02 32 ab dc 89 3e 7f 06 31 36 4d 7f d0 1c 0010 - b3 3d 24 da 45 32 9a 00 35 7b 3a 78 86 21 1a b4 0020 - 14 d5 5a 51 ae END

In other words, it's frame 03 to frame 06:

Frame 03: 1(0x51) Frame 04: 0000 - 02 32 ab dc 89 3e 7f 06 31 36 4d 7f d0 1c b3 3d 0010 - 24 da 45 32 9a 00 35 7b 3a 78 86 21 1a b4 14 d5 0020 - 5a END Frame 05: 1(0x51) Frame 06: OP_CHECKMULTISIG(0xae)

Contrary to normal subscript generation, this subscript does not go to the end of the script (it doesn't include any part of the public key at all).

I am not sure why this is the case.