|
Title: OP_CHECKMULTISIG question Post by: TierNolan on April 26, 2014, 06:36:40 PM The wiki defines the opcode as
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 (https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp#L915) 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. Title: Re: OP_CHECKMULTISIG question Post by: etotheipi on April 26, 2014, 10:05:46 PM 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. Title: Re: OP_CHECKMULTISIG question Post by: TierNolan on April 26, 2014, 10:23:21 PM 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. 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. Title: Re: OP_CHECKMULTISIG question Post by: gmaxwell on April 26, 2014, 11:23:33 PM Yes, they have to be in order in order to pass.
|