OP_CHECKMULTISIG - how does it work?

[ByteCoin]

Firstly, what's the correct syntax? The comment in the code says

Code:

([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)

but how many signatures are present in [sig ...]? Is num_of_signatures the actual number of signatures provided or is it the number of valid signatures required for OP_CHECKMULTISIG to return true?

I'm reading the code for OP_CHECKMULTISIG in script.cpp. It allows for fewer signatures than public keys but seems to iterate through both the signatures and public keys without any attempt to find out which ones are missing. I don't see how this could work for even a 1 of 2 multisignature transaction in both cases where, in the first case the signature matches the first public key and in the second case the signature matches the second public key.

Even if both signatures are provided but one is just invalid, the verification will fail as nSigsCount will only be 1 and if the first verification fails, the other will not even be attempted.

Can anyone explain please? The issue is becoming relevant...

ByteCoin

[theymos]

If ScriptPubKey says:

Code:

2 KeyA KeyB KeyC 3 OP_CHECKMULTISIG

Then ScriptSig must provide signatures for exactly two of A-C, listed in order.

If ScriptPubKey says:

Code:

1 KeyA KeyB KeyC 3 OP_CHECKMULTISIG

Then ScriptSig must only provide one of A-C.

It's not sane to allow the scriptSig to provide the sig count, since it would be legal for them to set it to 0.

[ByteCoin]

Got it! Thanks! Seems obvious how the code works now. I don't know what I was thinking before!

listed in order.

This is what did it for some reason....

Anyway, so that this thread isn't a complete waste of time I'd like to observe that the current way of matching signatures to public keys is very wasteful of computation. For example, if you have a 1 of 100 multisignature then the code goes through the public keys sequentially trying to verify the signature until it either succeeds or runs out of public keys. As each transaction is verified each time it is relayed, wouldn't it make sense to indicate in the scriptSig the number of public keys to skip before attempting to verify the signature. This could be an (optional?) 1 byte parameter which would save a very large number of unnecessary signature verification attempts.

ByteCoin

[jackjack]

Got it! Thanks! Seems obvious how the code works now. I don't know what I was thinking before!

listed in order.

This is what did it for some reason....

Anyway, so that this thread isn't a complete waste of time I'd like to observe that the current way of matching signatures to public keys is very wasteful of computation. For example, if you have a 1 of 100 multisignature then the code goes through the public keys sequentially trying to verify the signature until it either succeeds or runs out of public keys. As each transaction is verified each time it is relayed, wouldn't it make sense to indicate in the scriptSig the number of public keys to skip before attempting to verify the signature. This could be an (optional?) 1 byte parameter which would save a very large number of unnecessary signature verification attempts.

ByteCoin

Non-standard transaction, thus never relayed
Problem solved

[ByteCoin]

Non-standard transaction, thus never relayed
Problem solved

It looks like it was necessary for me to qualify that the whole thread presupposes that a template allowing OP_CHECKMULTISIG in a transaction is added to the "standard" list for some reason in the near future.

ByteCoin

[Gavin Andresen]

I've been working on a proposal to enable {1,2}-of-{1,2,3} signatures-required as standard transaction types.

I'll start another thread with more information...