test: fix `keys_to_multisig_script` (P2MS) helper for n/k > 16 #28312

theStack · 2023-08-22T01:33:16Z

While reviewing #28307, I noticed that the test framework's key_to_multisig_script helper (introduced in #23305) is broken for pubkey count (n) and threshold (k) values larger than 16. This is due to the implementation currently enforcing a direct single-byte data push (using CScriptOp.encode_op_n), which obviously fails for values 17+. Fix that by passing the numbers directly to the CScript list, where it's automatically converted to minimally-encoded pushes (see class method CScript.__coerce_instance, branch isinstance(other, int)).

The second commit adds a unit test to ensure that the encoding is correct.

DrahtBot · 2023-08-22T01:33:18Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	tdb3, rkrux, achow101

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#28710 (Remove the legacy wallet and BDB dependency by achow101)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

luke-jr · 2023-08-23T17:35:26Z

Maybe add a functional test that would have failed too?

theStack · 2023-08-23T22:14:39Z

Maybe add a functional test that would have failed too?

Yeah, seems like a good idea. Added one in rpc_createmultisig which checks that the multisig script encoding (returned as 'redeemScript') is as expected for all possible n (1..20), only using n-of-n for now to keep it simple.

rkrux · 2024-03-19T11:12:30Z

test/functional/test_framework/script_util.py

+        self.assertEqual(len(normal_ms_script), 1 + 16*34 + 1 + 1)
+        self.assertTrue(normal_ms_script.startswith(bytes([OP_15])))
+        self.assertTrue(normal_ms_script.endswith(bytes([OP_16, OP_CHECKMULTISIG])))
+
+        # check correct encoding of P2MS script with n,k > 16
+        max_ms_script = keys_to_multisig_script([fake_pubkey]*20, k=19)
+        self.assertEqual(len(max_ms_script), 2 + 20*34 + 2 + 1)


Should we add a comment explaining the logic behind the math in these script length assert calls?
Or maybe refer an existing doc?

Trying to understand why is there this else block in coerce_instance here that encodes using pushdata.
@theStack Do you know the reason by chance?
https://github.com/bitcoin/bitcoin/blob/master/test/functional/test_framework/script.py#L451-L452

@rkrux Numbers between -1 and 16 inclusive can use the 1-byte OP_n opcodes. Larger numbers require a script push (which is 2 bytes for numbers up to 127).

nit: In case this file is touched, it might be clearer (as rkrux mentioned) to add a comment explicitly explaining the math, although this is just a nice-to-have since the addition breaks it out such that the reader is provided a hint (typical multisig script).
Author's preference.

diff --git a/test/functional/test_framework/script_util.py b/test/functional/test_framework/script_util.py index 855f3b8cf5..69be490a67 100755 --- a/test/functional/test_framework/script_util.py +++ b/test/functional/test_framework/script_util.py @@ -133,7 +133,7 @@ class TestFrameworkScriptUtil(unittest.TestCase): fake_pubkey = bytes([0]*33) # check correct encoding of P2MS script with n,k <= 16 normal_ms_script = keys_to_multisig_script([fake_pubkey]*16, k=15) - self.assertEqual(len(normal_ms_script), 1 + 16*34 + 1 + 1) + self.assertEqual(len(normal_ms_script), 1 + 16*34 + 1 + 1) # OP_k + 16*[OP_PUSHBYTES_33 + 33 byte compressed pubkey] + OP_n + OP_CHECKMULTISIG self.assertTrue(normal_ms_script.startswith(bytes([OP_15]))) self.assertTrue(normal_ms_script.endswith(bytes([OP_16, OP_CHECKMULTISIG])))

rkrux · 2024-03-19T11:19:14Z

test/functional/rpc_createmultisig.py

+        self.log.info('Check correct encoding of multisig script for all n (1..20)')
+        for nkeys in range(1, 20+1):


Nit: Checking for integers between 15 and 17 would also suffice, right?

rkrux · 2024-03-19T11:19:32Z

test/functional/rpc_createmultisig.py

+            # note that the 'legacy' address type fails for n values larger than 15
+            # due to exceeding the P2SH size limit (520 bytes), so we use 'bech32' instead
+            # (for the purpose of this encoding test, we don't care about the resulting address)


Thanks for adding the comment, helpful!

rkrux

Concept ACK d113709

Testing Methodology

Checked out PR
Built core
Ran make check
Ran test/functional/test_runner.py

rkrux · 2024-03-19T11:30:33Z

test/functional/rpc_createmultisig.py

+        self.log.info('Check correct encoding of multisig script for all n (1..20)')
+        for nkeys in range(1, 20+1):
+            keys = [self.pub[0]]*nkeys
+            expected_ms_script = keys_to_multisig_script(keys, k=nkeys)  # simply use n-of-n


Curious: Is it common to test the correctness of a test utility function against the response from the bitcoin node?

Good question. I'm not sure if it's really that common, but there was a wish to also test the utility function via a functional test (see comment #28312 (comment)) and it seemed to be a worthwhile idea to me.

tdb3

Great work catching the bug and making testing more robust.

ACK for d113709.

One inline recommendation to cover an additional related edge case.

tdb3 · 2024-04-09T01:09:32Z

test/functional/rpc_createmultisig.py

+            # (for the purpose of this encoding test, we don't care about the resulting address)
+            res = self.nodes[0].createmultisig(nrequired=nkeys, keys=keys, address_type='bech32')
+            assert_equal(res['redeemScript'], expected_ms_script.hex())
+


Since > 20 keys are not allowed when creating a multisig address, recommend adding a test case to check this.

Something like:

diff --git a/test/functional/rpc_createmultisig.py b/test/functional/rpc_createmultisig.py index 4bbd2a526d..88f4e44a65 100755 --- a/test/functional/rpc_createmultisig.py +++ b/test/functional/rpc_createmultisig.py @@ -129,6 +129,9 @@ class RpcCreateMultiSigTest(BitcoinTestFramework): res = self.nodes[0].createmultisig(nrequired=nkeys, keys=keys, address_type='bech32') assert_equal(res['redeemScript'], expected_ms_script.hex()) + self.log.info('Check that number of keys greater than 20 is not allowed') + assert_raises_rpc_error(-8, "Number of keys involved in the multisignature address creation > 20", self.nodes[0].createmultisig, 20, [self.pub[0]]*21, "bech32") + def check_addmultisigaddress_errors(self): if self.options.descriptors: return

Such a test case was already introduced in the recently merged PR #28307 (commit 9be6065). Note that this PR is primarily focused on the keys_to_multisig_script helper in the test framework and only uses the createmultisig RPC to verify it.

The helper assumes that the n and k values have to be provided as a single byte push operation, which is only possible for values up to 16. Fix that by passing the numbers directly to the CScript list, where it's automatically converted to minimally-encoded pushes (see class method `CScript.__coerce_instance`, branch `isinstance(other, int)`). In case of 17..20, this means that the data-pushes are done with two bytes using OP_PUSH1 (0x01), e.g. for n=20: 0x01,0x14

theStack · 2024-06-05T14:22:48Z

Rebased on master.

tdb3

ACK 5cf0a1f
Re-ran functional tests (passed) and induced a failure by hard-coding 1 as the k value.

tdb3 · 2024-06-07T17:00:24Z

test/functional/test_framework/script_util.py

+        self.assertEqual(len(normal_ms_script), 1 + 16*34 + 1 + 1)
+        self.assertTrue(normal_ms_script.startswith(bytes([OP_15])))
+        self.assertTrue(normal_ms_script.endswith(bytes([OP_16, OP_CHECKMULTISIG])))
+
+        # check correct encoding of P2MS script with n,k > 16
+        max_ms_script = keys_to_multisig_script([fake_pubkey]*20, k=19)
+        self.assertEqual(len(max_ms_script), 2 + 20*34 + 2 + 1)


nit: In case this file is touched, it might be clearer (as rkrux mentioned) to add a comment explicitly explaining the math, although this is just a nice-to-have since the addition breaks it out such that the reader is provided a hint (typical multisig script).
Author's preference.

diff --git a/test/functional/test_framework/script_util.py b/test/functional/test_framework/script_util.py index 855f3b8cf5..69be490a67 100755 --- a/test/functional/test_framework/script_util.py +++ b/test/functional/test_framework/script_util.py @@ -133,7 +133,7 @@ class TestFrameworkScriptUtil(unittest.TestCase): fake_pubkey = bytes([0]*33) # check correct encoding of P2MS script with n,k <= 16 normal_ms_script = keys_to_multisig_script([fake_pubkey]*16, k=15) - self.assertEqual(len(normal_ms_script), 1 + 16*34 + 1 + 1) + self.assertEqual(len(normal_ms_script), 1 + 16*34 + 1 + 1) # OP_k + 16*[OP_PUSHBYTES_33 + 33 byte compressed pubkey] + OP_n + OP_CHECKMULTISIG self.assertTrue(normal_ms_script.startswith(bytes([OP_15]))) self.assertTrue(normal_ms_script.endswith(bytes([OP_16, OP_CHECKMULTISIG])))

rkrux

reACK 5cf0a1f

Re-ran make and all functional tests, both are successful.
Thanks @theStack for catching this.

achow101 · 2024-06-17T19:10:03Z

ACK 5cf0a1f

DrahtBot added the Tests label Aug 22, 2023

theStack force-pushed the test-fix_keys_to_multisig_for_17+ branch 2 times, most recently from 73c2def to 85c01bd Compare August 22, 2023 09:57

DrahtBot mentioned this pull request Aug 24, 2023

rpc, wallet: fix incorrect segwit redeem script size limit #28307

Merged

DrahtBot added CI failed and removed CI failed labels Sep 3, 2023

DrahtBot added CI failed and removed CI failed labels Sep 14, 2023

DrahtBot mentioned this pull request Sep 25, 2023

test: Use test framework utils in functional tests #28528

Closed

DrahtBot mentioned this pull request Oct 24, 2023

Remove the legacy wallet and BDB dependency #28710

Merged

DrahtBot added the CI failed label Jan 12, 2024

theStack force-pushed the test-fix_keys_to_multisig_for_17+ branch from 16269ef to d113709 Compare January 22, 2024 12:40

DrahtBot removed the CI failed label Jan 22, 2024

DrahtBot added CI failed and removed CI failed labels Mar 8, 2024

rkrux reviewed Mar 19, 2024

View reviewed changes

DrahtBot mentioned this pull request Mar 31, 2024

test: Run framework unit tests in parallel #29771

Merged

tdb3 reviewed Apr 9, 2024

View reviewed changes

DrahtBot requested a review from rkrux April 9, 2024 01:11

bitcoin deleted a comment from Ashflower13 Apr 9, 2024

DrahtBot added CI failed Needs rebase and removed CI failed labels Apr 21, 2024

theStack added 3 commits June 5, 2024 16:15

test: add unit test for keys_to_multisig_script

0570d2c

test: add createmultisig P2MS encoding test for all n (1..20)

5cf0a1f

theStack force-pushed the test-fix_keys_to_multisig_for_17+ branch from d113709 to 5cf0a1f Compare June 5, 2024 14:21

DrahtBot removed the Needs rebase label Jun 5, 2024

tdb3 approved these changes Jun 7, 2024

View reviewed changes

rkrux approved these changes Jun 15, 2024

View reviewed changes

achow101 merged commit 4bcef32 into bitcoin:master Jun 17, 2024

theStack deleted the test-fix_keys_to_multisig_for_17+ branch July 15, 2024 19:24

bitcoin locked and limited conversation to collaborators Jul 15, 2025

		self.log.info('Check correct encoding of multisig script for all n (1..20)')
		for nkeys in range(1, 20+1):

test: fix keys_to_multisig_script (P2MS) helper for n/k > 16 #28312

test: fix keys_to_multisig_script (P2MS) helper for n/k > 16 #28312

Uh oh!

Conversation

theStack commented Aug 22, 2023

Uh oh!

DrahtBot commented Aug 22, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage

Reviews

Conflicts

Uh oh!

luke-jr commented Aug 23, 2023

Uh oh!

theStack commented Aug 23, 2023

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rkrux left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Testing Methodology

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tdb3 left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

theStack commented Jun 5, 2024

Uh oh!

tdb3 left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rkrux left a comment

Choose a reason for hiding this comment

Uh oh!

achow101 commented Jun 17, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

test: fix `keys_to_multisig_script` (P2MS) helper for n/k > 16 #28312

test: fix `keys_to_multisig_script` (P2MS) helper for n/k > 16 #28312

DrahtBot commented Aug 22, 2023 •

edited

Loading

rkrux left a comment •

edited

Loading

tdb3 left a comment •

edited

Loading