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

<p>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. </p>

<p>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. </p>

<p>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. </p>

<p>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. </p>

<p>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)</p>

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

<p>At the end, it pushes a boolean indicating the return value.</p>

<p>The source code for this opcode can be found here: <a href="https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp" rel="nofollow">https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp</a></p>

CC BY-SA 3.0
2015-09-27T08:25:43.630Z
Thanks for giving me the push into the right direction to understand what exactly is going on!
Bjarne Magnussen
CC BY-SA 3.0
2015-09-26T20:14:42.077Z
2015-09-26T20:14:42.077Z
karimkorun
<blockquote>
  <p>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?</p>
</blockquote>

<p>That's not really how it's <a href="https://github.com/bitcoin/bitcoin/blob/48efbdbe986355bd2478f0fdd366b20952fbf30a/src/script/interpreter.cpp#L862" rel="noreferrer">implemented internally</a>, so there are a couple of pitfalls if you imagine it operating like that.</p>

<h3>OP_CHECKMULTISIG</h3>

<p>Here's the high-level description of how it works:</p>

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

<ol>
<li>For each public key, check a single signature.</li>
<li>For the first public key checked, start with the signature closest to the top of the stack.</li>
<li>If it fails to verify, go to the next public key and check the same signature.</li>
<li><p>If it succeeds, go to the next public key with the next signature.</p>

<p>Note that the signatures need to be in the same order as the key's that they're signing for.</p></li>
</ol></li>
<li>If all of the signatures succeeded with one of the keys, CHECKMULTISIG returns 1, otherwise 0.</li>
</ol>

<h3>Your example</h3>

<p>You've got this scriptSig:</p>

<pre><code>    (sig2)
    (sig1)
    0
</code></pre>

<p>This scriptPubKey:</p>

<pre><code>    3
    (pubKey3)
    (pubKey2)
    (pubKey1)
    2
</code></pre>

<p>When executing, the stack looks like this just before OP_CHECKMULTISIG executes:</p>

<pre><code>    3
    (pubKey3)
    (pubKey2)
    (pubKey1)
    2
    (sig2)
    (sig1)
    0
</code></pre>

<p>This is what it looks like after initializing:</p>

<pre><code>n-&gt;    3
ikey-&gt; (pubKey3)
       (pubKey2)
       (pubKey1)
m-&gt;    2
isig-&gt; (sig2)
       (sig1)
       0
</code></pre>

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

<pre><code>n-&gt;    3
       (pubKey3)
ikey-&gt; (pubKey2)
       (pubKey1)
m-&gt;    2
isig-&gt; (sig2)
       (sig1)
       0
</code></pre>

<p>Verifying pubKey2 against sig2 suceeds, so you advance both ikey and isig:</p>

<pre><code>n-&gt;    3
       (pubKey3)
       (pubKey2)
ikey-&gt; (pubKey1)
m-&gt;    2
       (sig2)
isig-&gt; (sig1)
       0
</code></pre>

<p>...and so on.</p>

CC BY-SA 3.0
2016-04-15T11:09:22.027Z
I can't add a comment to Nick ODell so I do it here, a tiny nano pocket error : "It tries to verify pubKey3 against **sig2**, but that fails. Advance ikey, but not isig:" Instead of : "It tries to verify pubKey3 against **sig1**, but that fails. Advance ikey, but not isig:"
onepix
CC BY-SA 3.0
2015-09-27T08:24:44.360Z
Thank you so much! This example has helped me a lot to understand what is really going on in the C++ Code of Bitcoin!
Bjarne Magnussen
CC BY-SA 3.0
2015-09-26T20:29:59.280Z
2016-08-31T20:52:34.823Z
2016-08-31T20:52:34.823Z
Nick ODell
<p>I was wondering if somebody could point me to or give me a worked out example of how OP_CHECKMULTISIG works behind the curtains?</p>

<p>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?</p>

<p>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:</p>

<ul>
<li>(sig2)</li>
<li>(sig1)</li>
<li>0</li>
</ul>

<p>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:</p>

<ul>
<li>3</li>
<li>(pubKey3)</li>
<li>(pubKey2)</li>
<li>(pubKey1)</li>
<li>2</li>
</ul>

<p>What exactly will the first step be of CHECKMULTISIG? </p>

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

<p>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? </p>

<p>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"? </p>

<p>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"?</p>

<p>I would really like to find a low-level description of CHECKMULTISIG, similarly to the one I could find for CHECKSIG:
<a href="https://en.bitcoin.it/wiki/OP_CHECKSIG" rel="noreferrer">https://en.bitcoin.it/wiki/OP_CHECKSIG</a></p>

<p>Any help would be very appreciated!</p>

CC BY-SA 3.0
2015-09-26T15:38:18.287Z
https://en.bitcoin.it/wiki/BIP_0011
Claris
<script><multi-signature>
CHECKMULTISIG a worked out example
Bjarne Magnussen
# CHECKMULTISIG a worked out example

(Asked by: username_0 on 2015-09-26)

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!

**Tags:** script, multi-signature

> **Comments:**
> **username_1**: https://en.bitcoin.it/wiki/BIP_0011  

---

## 2 answers

### Answer by username_3 on 2015-09-26. Score: 15 | Accepted answer

> 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](https://github.com/bitcoin/bitcoin/blob/48efbdbe986355bd2478f0fdd366b20952fbf30a/src/script/interpreter.cpp#L862), 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.

> **Comments:**
> **username_0**: Thank you so much! This example has helped me a lot to understand what is really going on in the C++ Code of Bitcoin!  
> **username_4**: I can't add a comment to username_3 username_3 so I do it here, a tiny nano pocket error : "It tries to verify pubKey3 against **sig2**, but that fails. Advance ikey, but not isig:" Instead of : "It tries to verify pubKey3 against **sig1**, but that fails. Advance ikey, but not isig:"  

---

### Answer by username_2 on 2015-09-26. Score: 4

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>

> **Comments:**
> **username_0**: Thanks for giving me the push into the right direction to understand what exactly is going on!  

---

