Expected behavior (conceptual):

18. The Off-By-One Bug in OP_CHECKMULTISIG

The Bug

OP_CHECKMULTISIG has a well-known implementation bug: it pops one extra element from the stack beyond what the algorithm actually needs. When Satoshi implemented the opcode, the code consumed M signatures, N public keys, and the M/N values — but also consumed one additional stack element that serves no algorithmic purpose.

# Expected behavior (conceptual):
pop N (number of pubkeys)
pop N pubkeys
pop M (number of required sigs)
pop M signatures
# Done — stack consumed what was needed

# Actual behavior (with bug):
pop N
pop N pubkeys
pop M
pop M signatures
pop ONE_MORE_ELEMENT  ← This extra pop is the bug

Why It's a Consensus Rule Now

This bug was discovered early in Bitcoin's history. Rather than fixing it (which would have broken backward compatibility and required a hard fork), Satoshi and the community decided to formalize it as a consensus rule. Fixing it would mean scripts that relied on the buggy behavior would break.

The bug is now REQUIRED behavior.
Any implementation that does NOT consume the extra element
would be consensus-incompatible.

The Workaround: OP_0 as the Dummy Element

The standard workaround is to push OP_0 (an empty byte array) as the extra element at the bottom of the signature stack:

# Correct unlocking script for 2-of-3 multisig:
OP_0        ← Dummy element consumed by the bug
<sig1>
<sig2>

# If you forget OP_0:
<sig1>
<sig2>
→ After consuming sig1, sig2, and the M/N values,
  the extra pop tries to consume from an empty (or unexpected) stack
  → SCRIPT FAILS

Historical Context

The bug was present in the very first multisig transactions on the Bitcoin network. The standard OP_0 workaround was documented in BIP 11 (M-of-N Standard Transactions) in 2012.

# From BIP 11:
"Because of a bug in the reference implementation, OP_CHECKMULTISIG consumes
 one more item than it should from the stack. Pushing a dummy value prevents
 this from being a problem in practice."

Non-Standard Extra Elements

While OP_0 is the standard dummy element, any data value technically works (since the extra element is just discarded). However, nodes running IsStandardTx() checks only accept OP_0:

Standard (relayed by default nodes):
  OP_0 <sig1> <sig2> <redeemScript>

Non-standard (may not relay but consensus-valid):
  OP_1 <sig1> <sig2> <redeemScript>  ← Works but non-standard
  <any_data> <sig1> <sig2> ...        ← Works but non-standard

NULLFAIL Rule (BIP 146)

BIP 146 introduced the NULLFAIL rule: if OP_CHECKMULTISIG fails (returns false), all provided signatures must be empty byte arrays. This prevents a class of signature malleability attacks where an attacker could replace a valid signature with an invalid one:

def apply_nullfail(sigs, result):
    if not result:
        for sig in sigs:
            if sig != b'':
                raise ScriptError("NULLFAIL: non-empty sig in failed CHECKMULTISIG")

OP_CHECKMULTISIG vs OP_CHECKSIGADD (Tapscript)

The off-by-one bug was one of the motivations for introducing OP_CHECKSIGADD in Tapscript, which provides cleaner multisig semantics without the dummy element requirement.

Legacy:     OP_0 <sig1> <sig2> OP_2 <pk1> <pk2> <pk3> OP_3 OP_CHECKMULTISIG
Tapscript:  <sig1> <sig2> OP_0 <pk1> OP_CHECKSIGADD <pk2> OP_CHECKSIGADD <pk3>
            OP_CHECKSIGADD OP_2 OP_GREATERTHANOREQUAL