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.
Wouldn't nodes just drop transactions that aren't valid? So an attacker won't be able to do much damage since those transactions would not propagate. We could even do more checking such that if any of the checksigs fail, we fail the transaction. So the attacker can't send a transaction with 2 bad signatures and 1 good one.
0
SWAP DUP 0NOTEQUAL NOTIF pubkey CHECKSIGVERIFY 1 ENDIF ADD // n times
m GREATERTHANOREQUAL
In terms of opcodes, it's about the same. But the general case can handle complicated requirements much better. You don't need to handle every possible case and the redeemer does not really need to know which case he satisfies.
For example, the "(a and b) or c" case:
0
SWAP DUP 0NOTEQUAL NOTIF pubkeyc CHECKSIGVERIFY 2 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeyb CHECKSIGVERIFY 1 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeya CHECKSIGVERIFY 1 ENDIF ADD
2 GREATERTHANOREQUAL
The current proposed 2-of-3 case is complicated. The redeemer needs to know which case he's satisfying. How would this information be stored in the wallet?
DUP NOTIF DROP pubkeyb CHECKSIGVERIFY pubkeya CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DUP NOTIF DROP pubkeyc CHECKSIGVERIFY pubkeyb CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DUP NOTIF DROP pubkeyc CHECKSIGVERIFY pubkeya CHECKSIG TOALTSTACK 0 ENDIF 1SUB
DROP FROMALTSTACK
My proposed general 2-of-3 case is much simpler and uses less opcodes. The redeemer just needs to know, for example, that he has keya and keyc. So he just does "keya OP_0 keyc" to redeem. He does not need to know that his transaction actually satisfies the 3rd case.
0
SWAP DUP 0NOTEQUAL NOTIF pubkeyc CHECKSIGVERIFY 1 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeyb CHECKSIGVERIFY 1 ENDIF ADD
SWAP DUP 0NOTEQUAL NOTIF pubkeya CHECKSIGVERIFY 1 ENDIF ADD
2 GREATERTHANOREQUAL
If you are still not convinced, think of what the 3-of-5 case will look like for both.