op_checkmultisig: Last signature is not verified

[koirikivi]

The given answer for op_checkmultisig in Chapter 8 has a bug where the last signature is never verified:

def op_checkmultisig(stack, z):
    ...
    try:
        points = [S256Point.parse(sec) for sec in sec_pubkeys]
        sigs = [Signature.parse(der) for der in der_signatures]
        for sig in sigs:
            if len(points) == 0:
                return False
            while points:
                point = points.pop(0)
                if point.verify(z, sig):
                    break
        stack.append(encode_num(1))
    except (ValueError, SyntaxError):
        return False
    return True

The fail condition is in the following check:

            if len(points) == 0:
                return False

but it is only executed at the beginning of each iteration and crucially NOT after we have iterated over all sigs. So if we have a 1-of-1 op_checkmultisig, it will pass with any signature and any pubkey, and if we have a 2-of-2 op_checkmultisig, it will pass as long as the first checked signature matches the first checked pubkey (and so on).

Example test code to reproduce

    def test_op_checkmultisig2(self):
        z = 0xe71bfa115715d6fd33796948126f40a8cdd39f187e4afb03896795189fe1423c
        sig1 = bytes.fromhex('3045022100dc92655fe37036f47756db8102e0d7d5e28b3beb83a8fef4f5dc0559bddfb94e02205a36d4e4e6c7fcd16658c50783e00c341609977aed3ad00937bf4ee942a8993701')
        sig2 = bytes.fromhex('3045022100da6bee3c93766232079a01639d07fa869598749729ae323eab8eef53577d611b02207bef15429dcadce2121ea07f233115c6f09034c0be68db99980b9a6c5e75402201')
        sec1 = bytes.fromhex('022626e955ea6ea6d98850c994f9107b036b1334f18ca8830bfff1295d21cfdb70')
        stack = [b'', sig1, b'\x01', sec1, b'\x01']
        # This is ok, 1 of 1 multisig with the correct signature
        self.assertTrue(op_checkmultisig(stack, z))
        self.assertEqual(decode_num(stack[0]), 1)
        # This should fail, 1 of 1 multisig with wrong signature
        stack = [b'', sig2, b'\x01', sec1, b'\x01']
        self.assertFalse(op_checkmultisig(stack, z))
        # This should also fail, 2 of 2 multisig with 1 wrong signature (sig2 is checked last)
        stack = [b'', sig2, sig1, b'\x02', sec1, sec1, b'\x02']
        self.assertFalse(op_checkmultisig(stack, z))

Relates to #214 as that issue also talks about problems with op_checkmultisig.

From my understanding, the signatures passed to op_checkmultisig need to be in the same order as the pubkeys. If that's the case, we can fix the implementation using the while ... else construct:

def op_checkmultisig(stack, z):
    ...
    try:
        points = [S256Point.parse(sec) for sec in sec_pubkeys]
        sigs = [Signature.parse(der) for der in der_signatures]
        for sig in sigs:
            if len(points) == 0:
                return False
            while points:
                point = points.pop(0)
                if point.verify(z, sig):
                    break
            else:
                return False
        stack.append(encode_num(1))
    except (ValueError, SyntaxError):
        return False
    return True

[mattacus]

Here is the way I went about it, I saw that about the signatures being in the same order of the pubkeys. But, I'm not quite sure why that is necessary so long as: 1) Each signature can be verified against one of the pubkeys successfully, and 2) The pubkey is removed from the list once it is matched with a signature

I solved it using list .remove(). I don't think things necessarily have to be in order. It seems to cover all the test cases I've tried. Am I missing something or would this work just as well?

try:
        pubkeys_parsed = [S256Point.parse(p) for p in sec_pubkeys]
        signatures_parsed = [Signature.parse(p) for p in signatures]
        for sig in signatures_parsed:
            if len(pubkeys_parsed) == 0:
                return False
            signature_verified = False
            for pubkey in pubkeys_parsed:
                if pubkey.verify(z, sig):
                    print(f'Verified point: {pubkey} with signature: {sig}')
                    signature_verified = True
                    pubkeys_parsed.remove(pubkey)
                    break
            if not signature_verified:
                return False  # Signature did not match a pubkey
        stack.append(encode_num(1))

[koirikivi]

@mattacus From my understanding, the actual implementation of op_checkmultisig in Bitcoin requires the signatures and pubkeys to be in the same order. At least according to these sources:

• https://bitcoin.stackexchange.com/questions/113425/order-of-signatures-in-multisig-scheme
• https://en.bitcoin.it/wiki/OP_CHECKMULTISIG

[mattacus]

Right, I saw that, in the docs:

Because public keys are not checked again if they fail any signature comparison, signatures must be placed in the scriptSig using the same order as their corresponding public keys

After thinking about it some more it makes more sense to do it that way since signature verification time could add up if you have, say, 100s of signature that each node must verify, and you don't pop each pubkey each time it is visited. (In my case I am removing them, but only if the signature is verified, so there could be more iterations). So it seems like they chose that approach for efficiency reasons.