Currently with OP_CHECKMULTISIG we have the following N-of-M mechanics (legacy mechanics), illustrated by a 2-of-3 example:
- Locking script:
OP_2 pubkey_alice pubkey_bob pubkey_carol OP_3 OP_CHECKMULTISIG - ScriptSig (N+1 pushes):
OP_0 sig_alice sig_carol(OP_0 is the dummy element)
This is a rather bad mechanism, where sig_carol needs to be checked against both pubkey_bob and pubkey_carol. As discussed elsewhere, this is a disaster for Schnorr batch verification. So in the May 2019 upgrade, we're going to make it so that the signatures sig_alice and sig_carol are not allowed to be Schnorr signatures. I mean, we could allow them to be Schnorr and just use single-checking, but we have better plans in mind...
Schnorr signature aggregates (with OP_CHECKSIG) are really cool but they aren't a replacement for OP_CHECKMULTISIG. So, we need a new way that at least allows for batch verification.
Our goal is to make it so that all UTXOs can be spent with Schnorr, and that includes multisigs. It is unthinkable to change anything in the locking script from above, because that is what defines a typical multisig UTXO. We can however change what appears in the ScriptSig. What kind of approaches could we adopt for the new mechanics that still lets people use legacy mechanics with ECDSA?
- Locking script:
OP_2 pubkey_alice pubkey_bob pubkey_carol OP_3 OP_CHECKMULTISIG - ScriptSig (M pushes):
sig_alice OP_0 sig_carol(OP_0 is placeholder for skipped pubkey)
This goes in the right direction -- just list signatures in order, one per pubkey; for non-signing parties, just put OP_0 to indicate that pubkey should be skipped. Now batch verification is possible again. The problem is that this is ambiguous:
- OP_CHECKMULTISIG is required to consume a correct amount of items from the stack and then push back OP_0 if it fails.
- The legacy mechanics uses N+1 pushes, and this uses M pushes. So you can't check ALL the stack items.
- You can't just check the top stack item, since it is legal for the top element to be OP_0 for OP_CHECKMULTISIG in legacy mechanics (for false-returning) and new mechanics (for skipped pubkey).
- Specific example: what happens when you have a 2-of-6 multisig and the top 4 items of scriptSig are OP_0 OP_0 OP_0 OP_0? In the legacy mechanism, this is legal and means the OP_CHECKMULTISIG should consume 4 items and return False. For our new mechanism this is also legal (last four pubkeys skipped) but we have to consume 6 items (!), and depending on what the extra two items are, we might return True or False or it may be invalid. This ambiguity is no good.
- Locking script:
OP_2 pubkey_alice pubkey_bob pubkey_carol OP_3 OP_CHECKMULTISIG - ScriptSig (M+1 pushes):
sig_alice OP_0 sig_carol OP_1(The OP_0 is a placeholder for skipped pubkey. The OP_1 is the sentinel.)
This works well for N-of-M signatures for any N:
- N>=1. With current OP_CHECKMULTISIG mechanics, you cannot put OP_1 for a signature due to the NULLFAIL rule. With NULLFAIL, such bad signatures do not make the opcode return false. Instead, they make the entire script and transaction invalid.
- N=0 (degenerate, but allowed). In legacy mechanics, just one item (the dummy element) gets consumed from the stack. The new mechanics also just consume one item. So, there is no ambiguity here.
It is possible to use any of OP1...OP_16 or OP_1NEGATE for the placeholder, as they can all be nicely pushed with a 1-byte opcode. It would be a good idea to examine the past blockchain to see which of these have not been used in this position before NULLFAIL activated. If we can find an unused one, then it leads to cleaner activation mechanics. Once activated, it would be possible to remove the activation flags and have the new mechanics apply retroactively.
- Locking script:
OP_2 pubkey_alice pubkey_bob pubkey_carol OP_3 OP_CHECKMULTISIG - ScriptSig (N+1 pushes):
sig_alice sig_carol Z
If it is desired to reduce the number of pushes and bytes to the absolute minimum, this approach can be used. Here, Z is an unsigned nonzero integer. For OP_CHECKMULTISIG there are only (M choose N)+1 possibilities to have a signature: M choose N ways to return True, and 1 way to return False. These (M choose N)+1 possibilities can be enumerated as a nonzero integer Z and then pushed in the most compact way. Note that single-byte Z=0 is not allowed since that is interpreted as a legal missing signature in the legacy mechanics.
In this way, only N+1 pushes are required, and Z can be encoded as a single byte (between OP_1 and OP_16) for up to M=5 parties (also 4-of-6, but not 3-of-6), or as two bytes (OP_PUSH <1 byte>) for up to M=10 parties (also 8-of-11, but not 4-of-11 or 5-of-11 or 6-of-11 or 7-of-11).