Locking script

Stack before OP_CHECKMULTISIG (bottom to top):
  <OP_0>     ← dummy element (required due to bug — see topic 18)
  <sig1>
  <sig2>
  ...
  <sigM>
  <M>        ← minimum signatures required
  <pubkey1>
  <pubkey2>
  ...
  <pubkeyN>
  <N>        ← total public keys  ← TOP OF STACK

# Locking script
OP_2
<pubKey1>
<pubKey2>
<pubKey3>
OP_3
OP_CHECKMULTISIG

# Unlocking script (must include OP_0 due to the off-by-one bug)
OP_0
<sig1>
<sig2>

scriptPubKey:
  OP_1 <pubKeyA> <pubKeyB> OP_2 OP_CHECKMULTISIG

scriptSig:
  OP_0 <sigA>   (or <sigB>)

def checkmultisig(sigs, pubkeys, tx, input_index):
    """
    Greedy matching: iterate signatures against public keys in order.
    A pubkey, once matched, is consumed (cannot match multiple sigs).
    Order matters: sigs must be in same order as their pubkeys.
    """
    sigs_remaining = list(sigs)
    pubkeys_remaining = list(pubkeys)

    while sigs_remaining and pubkeys_remaining:
        sig = sigs_remaining[0]
        pubkey = pubkeys_remaining[0]

        if verify_sig(sig, pubkey, tx, input_index):
            sigs_remaining.pop(0)  # This sig matched, consume it

        pubkeys_remaining.pop(0)  # Consume pubkey regardless

    return len(sigs_remaining) == 0  # All sigs must have matched

Public keys: [Alice, Bob, Carol]
Valid:   OP_0 <Alice_sig> <Bob_sig>
Valid:   OP_0 <Alice_sig> <Carol_sig>
Valid:   OP_0 <Bob_sig> <Carol_sig>
INVALID: OP_0 <Bob_sig> <Alice_sig>   ← Wrong order!

Maximum N: 20 public keys (consensus rule)
Maximum M: 20 (but M ≤ N required)
Script size limit: 10,000 bytes
Signature operations: Each CHECKMULTISIG counts as N sigops
  (or 20 sigops if N is not a data push — worst case)

# P2SH sigop counting:
# Standard 2-of-3: counts as 3 sigops (N value)
# Non-standard: counts as 20 sigops