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