Chapter 8 - Bare Multisig doesn't mention public keys and signatures need to be in the matching order

[amadeann]

Section "Bare Multisig" doesn't mention that public keys and signatures used as arguments to OP_CHECKMULTISIG need to be in the matching order.

In particular, I am referring to the proposed solution to Exercise 1 - without the assumption that keys and signatures are in the specific order, the exercise cannot be solved this way:

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))

[sjorsvanheuveln]

Yes, this appears not be right. The problem here also is that m and n are not being used. The code now just checks whether the first signature has a public key that can verify it.

[xu-kai-xu]

@sjorsvanheuveln @amadeann @jimmysong Hi, I also find this problem. I think it is the directly points.pop(0) code leads to the problem. If for the first sig, the points are all popped out, then for the next sig, there is no points for verification. So I modify the related code snippets and the test code, as follows:

realization 1

for sig in sigs:
    results = []
    for point in points:
        if point.verify(z, sig):
            results.append(True)
        else:
            results.append(False)
    if True not in results:
        return False

realization 2

points_tmp = points[:]
for sig in sigs:
    if len(points_tmp) == 0:
        return False
    while points_tmp:
        point = points_tmp.pop(0)
        if point.verify(z, sig):
            points_tmp = points[:]
            break

test code

def test_op_checkmultisig(self):
    z = 0xe71bfa115715d6fd33796948126f40a8cdd39f187e4afb03896795189fe1423c
    sig1 = bytes.fromhex('3045022100dc92655fe37036f47756db8102e0d7d5e28b3beb83a8fef4f5dc0559bddfb94e02205a36d4e4e6c7fcd16658c50783e00c341609977aed3ad00937bf4ee942a8993701')
    sig2 = bytes.fromhex('3045022100da6bee3c93766232079a01639d07fa869598749729ae323eab8eef53577d611b02207bef15429dcadce2121ea07f233115c6f09034c0be68db99980b9a6c5e75402201')
    # sig3 and sig4 are based on sig 1 and 2, and change one number
    sig3 = bytes.fromhex('3045022100dc92655fe27036f47756db8102e0d7d5e28b3beb83a8fef4f5dc0559bddfb94e02205a36d4e4e6c7fcd16658c50783e00c341609977aed3ad00937bf4ee942a8993701')
    sig4 = bytes.fromhex('3045022100da6bee3c92766232079a01639d07fa869598749729ae323eab8eef53577d611b02207bef15429dcadce2121ea07f233115c6f09034c0be68db99980b9a6c5e75402201')

    sec1 = bytes.fromhex('022626e955ea6ea6d98850c994f9107b036b1334f18ca8830bfff1295d21cfdb70')
    sec2 = bytes.fromhex('03b287eaf122eea69030a0e9feed096bed8045c8b98bec453e1ffac7fbdbd4bb71')
    sec3 = bytes.fromhex('04887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e4da568744d06c61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34')
    stack1 = [b'', sig2, sig1, b'\x02', sec1, sec2, sec3, b'\x03']
    stack2 = [b'', sig2, sig3, b'\x02', sec1, sec2, sec3, b'\x03']
    stack3 = [b'', sig4, sig3, b'\x02', sec1, sec2, sec3, b'\x03']
    self.assertTrue(op_checkmultisig(stack1, z))
    self.assertFalse(op_checkmultisig(stack2, z))
    self.assertFalse(op_checkmultisig(stack3, z))
    self.assertEqual(decode_num(stack1[0]), 1)

[koirikivi]

If I understood things correctly, the op_checkmultisig implementation from the book has other issues too. See #270

(At least according to https://bitcoin.stackexchange.com/a/113428, the order of signatures is important, which would mean that the other solutions in this issue are not correct. However, I couldn't find a more satisfactory source for this.)

[MolekoManyanye]

If I understood things correctly, the op_checkmultisig implementation from the book has other issues too. See #270

(At least according to https://bitcoin.stackexchange.com/a/113428, the order of signatures is important, which would mean that the other solutions in this issue are not correct. However, I couldn't find a more satisfactory source for this.)

the implementation is so that we dont run into very long loops. imagen providing 100 wrong signatures to 130 pubkeys, then for each sig we would need to loop 130 times. that is 13 000 times loops in total . but the implementation in the book guarantees the worst loop length to be 130. This is adhering to the turing completness