CHECKMULTISIG a worked out example 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!
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:


Pop n off of the stack (number of public keys)
Pop n public keys off of the stack.
Pop m off of the stack (number of required signatures)
Pop m signatures off of the stack.
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.)
Loop through all of the public keys, starting with the keys at the top of the stack.


For each public key, check a single signature.
For the first public key checked, start with the signature closest to the top of the stack.
If it fails to verify, go to the next public key and check the same signature.
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.

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-&gt;    3
ikey-&gt; (pubKey3)
       (pubKey2)
       (pubKey1)
m-&gt;    2
isig-&gt; (sig2)
       (sig1)
       0


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

n-&gt;    3
       (pubKey3)
ikey-&gt; (pubKey2)
       (pubKey1)
m-&gt;    2
isig-&gt; (sig2)
       (sig1)
       0


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

n-&gt;    3
       (pubKey3)
       (pubKey2)
ikey-&gt; (pubKey1)
m-&gt;    2
       (sig2)
isig-&gt; (sig1)
       0


...and so on.