CHECKMULTISIG a worked out example

Question

I was wondering if somebody could point me to or give me a worked out example of how OP_CHECKMULTISIG works behind the curtains?

I expect that CHECKMULTISIG will call the CHECKSIG function and manipulate the stack to run CHECKSIG in a loop until it terminates and either has its M-out-of-N valid sigs or not?

But how exactly does it work? E.g. for 2-of-3 multisig. If we have OP_0 (sig1) (sig2) in the scriptSig, then the stack will look like:

• (sig2)
• (sig1)
• 0

Now from the general way of writing CHECKMULTISIG in the scriptPubKey: 2 (pubKey1) (pubKey2) (pubKey3) 3 OP_CHECKMULTISIG, when pushing all the data onto the stack, the stack for the scriptPubKey will look like:

• 3
• (pubKey3)
• (pubKey2)
• (pubKey1)
• 2

What exactly will the first step be of CHECKMULTISIG?

Will it pop the "3" from the stack and then maybe check if there are three pubKeys on the stack?

Or will it just pop the "3" and then immediately run CHECKSIG on (sig2) and (pubKey3), which will not be valid, hence CHECKSIG will push a "0" on the stack?

Will then CHECKMULTISIG remove the "0" that CHECKSIG introduced on the stack and try again with (sig2) and (pubKey2)? Since this is valid CHECKSIG will push a "1" on the stack, but where does CHECKMULTISIG store this "1"?

And will CHECKMULTISIG at the end count how many "1"'s CHECKSIG made and this number must correspond to the last value on the stack, in this case "2", but in general "M"?

I would really like to find a low-level description of CHECKMULTISIG, similarly to the one I could find for CHECKSIG: https://en.bitcoin.it/wiki/OP_CHECKSIG

Any help would be very appreciated!

Answer 1

I expect that CHECKMULTISIG will call the CHECKSIG function and manipulate the stack to run CHECKSIG in a loop until it terminates and either has its M-out-of-N valid sigs or not?

That's not really how it's implemented internally, so there are a couple of pitfalls if you imagine it operating like that.

OP_CHECKMULTISIG

Here's the high-level description of how it works:

1. Pop n off of the stack (number of public keys)
2. Pop n public keys off of the stack.
3. Pop m off of the stack (number of required signatures)
4. Pop m signatures off of the stack.
5. Pop one more element off of the stack, and ignore it. (This is a bug, but it can't be fixed because this is consensus-critical code.)

6. Loop through all of the public keys, starting with the keys at the top of the stack.

   1. For each public key, check a single signature.
   2. For the first public key checked, start with the signature closest to the top of the stack.
   3. If it fails to verify, go to the next public key and check the same signature.

   4. If it succeeds, go to the next public key with the next signature.

      Note that the signatures need to be in the same order as the key's that they're signing for.

7. If all of the signatures succeeded with one of the keys, CHECKMULTISIG returns 1, otherwise 0.

Your example

You've got this scriptSig:

    (sig2)
    (sig1)
    0

This scriptPubKey:

    3
    (pubKey3)
    (pubKey2)
    (pubKey1)
    2

When executing, the stack looks like this just before OP_CHECKMULTISIG executes:

    3
    (pubKey3)
    (pubKey2)
    (pubKey1)
    2
    (sig2)
    (sig1)
    0

This is what it looks like after initializing:

n->    3
ikey-> (pubKey3)
       (pubKey2)
       (pubKey1)
m->    2
isig-> (sig2)
       (sig1)
       0

It tries to verify pubKey3 against sig2, but that fails. Advance ikey, but not isig:

n->    3
       (pubKey3)
ikey-> (pubKey2)
       (pubKey1)
m->    2
isig-> (sig2)
       (sig1)
       0

Verifying pubKey2 against sig2 suceeds, so you advance both ikey and isig:

n->    3
       (pubKey3)
       (pubKey2)
ikey-> (pubKey1)
m->    2
       (sig2)
isig-> (sig1)
       0

...and so on.

Answer 2

It's far simpler than relying on values pushed by OP_CHECKSIG internally! It calls the same function that OP_CHECKSIG uses - in a loop - after parsing the public key and required signature count.

The procedure starts by checking the stack's size. Next it takes the keyCount (at the top of the stack as you observed in your question), and limits the number to 20 or less. It stores the position of the first public key in the stack.

Taking the value at position (top - keyCount) should give you the number of signatures. Some sanity checks are now performed (the required number of signatures should not exceed the number of keys). It then stores the position of the first signature.

Next the software enters a loop: So long as none of the signatures fail, it takes the first signature and public key, validates their encoding, and calls the same function that OP_CHECKSIG uses to check the signature.

If validation succeeds, it will increment the signature counter. If it fails, this doesn't happen, so the loop will try this signature with the next key. But in either case, the public key counter is increased.

This means signatures need to be provided in the same order as the public keys. If a signature fails, try the next key. (Think about the ordering of signatures in a 2-of-3)

It will also check that the dummy null value exists, and optionally verifies that it actually is a byte of \x00.

At the end, it pushes a boolean indicating the return value.

The source code for this opcode can be found here: https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp