After much fruitful discussion and evolution, this proposal is now a series of "Bitcoin Improvement Proposals" -- see BIP 11, 12 and 13: https://en.bitcoin.it/wiki/Bitcoin_Improvement_Proposals
Sincere thanks to everybody who contributed improvements, ideas and code.
@casey-bowman - agreed, that's what I was trying to say
@coblee - you can't do 0NOTEQUAL on something that can be a signature because a signature cannot be casted to a CBigNum. The script will throw an exception and fail. Just do:
0
SWAP pubkeyc CHECKSIG ADD
SWAP pubkeyb CHECKSIG ADD
SWAP pubkeya CHECKSIG ADD
2 GREATERTHANOREQUAL
script.cpp doesn't actually run the heavy computational stuff when the input is zero.
I agree that "checking more signatures than needed" is not an attack mode, because the concept of "needed" is ill-defined. I could create a valid 5-of-5 transaction just for kicks even if I have no need for 5 signatures on it. The only way to get people to use what they need is to charge proportional transaction fees. That will be up to miners at some future point when CPU usage becomes an issue.
Miners can figure out the cost of evaluating the various scripts proposed here without executing them. Even with the version that doesn't use IF/ENDIF, we can figure out the cost of execution by counting the number of non-zero signatures in scriptSig. If we can figure out the cost of execution we can charge accordingly. Once miners start charging, it would incentivise users to just fill in the minimal number of signatures to evaluate to true.
A bad case would be when we can't efficiently figure out the real number of sig ops, but none of the proposals here have that property.