OP_CHECKMULTISIG question

[TierNolan]

The wiki defines the opcode as

For each signature and public key pair, OP_CHECKSIG is executed. If more public keys than signatures are listed, some key/sig pairs can fail. All signatures need to match a public key. If all signatures are valid, 1 is returned, 0 otherwise. Due to a bug, one extra unused value is removed from the stack.

This means that there is a need to check every signature against every public key.  This is O(N^2) performance.  In a 10 of 10 case, around 50 checks would be required.

In the code it appears to require that the keys and signatures are in the same order.

Assuming a 2 of 3 case, with 3 signatures a, b, c and 3 keys A, B and C,

a, c, A, B, C

would work, since a and c are in the right order.

c, a, A, B, C

would fail, since c and a are in the wrong order.

This is the loop.

The 2 counters isig and ikey are only ever incremented.  Each key is only every tested against 1 signature.  This means that the operation is O(N) performance rather than O(N^2).

Is this correct?

An additional optimisation could be added by using the extra multisig stack item.  In a 2 of 10 situation, all 10 keys might need to be checked.  The extra item that is popped off the stack could encode which public keys are used.  0x03 would mean that the last 2 public keys are used.  This would reduce the verification load.

In most cases, it is probably not that big a deal.

[etotheipi]

I did just verify this is true.   thought there was an OP_0 in there for every empty sig, but just verified there isn't on a confirmed 3-of-4 spend.

Luckily, it's not exactly O(N), because as long as the sigs are the in the right order, the mapping between the two lists converges quickly.  You will end up with extra/unnecessary signature checks, but you shouldn't need more than N.

I agree it could be improved by utilizing that first push-data, but keep in mind that value is a source of malleability.  I think we'd prefer to force it to always be OP_0, or force it to encode a canonical encoding like you recommend.  I doubt we'd do a softfork just for that change, though, so it will probably stay at OP_0.

[TierNolan]

I did just verify this is true.   thought there was an OP_0 in there for every empty sig, but just verified there isn't on a confirmed 3-of-4 spend.

Luckily, it's not exactly O(N), because as long as the sigs are the in the right order, the mapping between the two lists converges quickly.  You will end up with extra/unnecessary signature checks, but you shouldn't need more than N.

Right, it is basically 2 pointers to the two lists.  When a signature matches a key, that sig is confirmed and it moves on to the next signature.  The key pointer is updated every iteration.

Once all signatures have matched a key, it breaks out of the loop.

The maximum number of iterations is equal to the number of keys.

I agree it could be improved by utilizing that first push-data, but keep in mind that value is a source of malleability.  I think we'd prefer to force it to always be OP_0, or force it to encode a canonical encoding like you recommend.  I doubt we'd do a softfork just for that change, though, so it will probably stay at OP_0.

I agree, malleability is more important.  If it was O(N^2), then it would be worth it to force it to be the way it is now.

[gmaxwell]

Yes, they have to be in order in order to pass.