Topic: OP_CHECKMULTISIG question (Read 653 times)
Yes, they have to be in order in order to pass.
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.
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.
Quote
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.
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.
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.
The wiki defines the opcode as
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.
Quote
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.
Jump to: