diff --git a/doc/descriptors.md b/doc/descriptors.md --- a/doc/descriptors.md +++ b/doc/descriptors.md @@ -26,6 +26,7 @@ - Pay-to-pubkey-hash scripts (P2PKH), through the `pkh` function. - Pay-to-script-hash scripts (P2SH), through the `sh` function. - Multisig scripts, through the `multi` function. +- Multisig scripts where the public keys are sorted lexicographically, through the `sortedmulti` function. - Any type of supported address through the `addr` function. - Raw hex scripts through the `raw` function. - Public keys (compressed and uncompressed) in hex notation, or BIP32 extended pubkeys with derivation paths. @@ -37,6 +38,7 @@ - `combo(0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)` describes any P2PK or P2PKH output with the specified public key. - `multi(1,022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4,025cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc)` describes a bare *1-of-2* multisig output with keys in the specified order. - `sh(multi(2,022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01,03acd484e2f0c7f65309ad178a9f559abde09796974c57e714c35f110dfc27ccbe))` describes a P2SH *2-of-2* multisig output with keys in the specified order. +- `sh(sortedmulti(2,03acd484e2f0c7f65309ad178a9f559abde09796974c57e714c35f110dfc27ccbe,022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01))` describes a P2SH *2-of-2* multisig output with keys sorted lexicographically in the resulting redeemScript. - `pk(xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8)` describes a P2PK output with the public key of the specified xpub. - `pkh(xpub68Gmy5EdvgibQVfPdqkBBCHxA5htiqg55crXYuXoQRKfDBFA1WEjWgP6LHhwBZeNK1VTsfTFUHCdrfp1bgwQ9xv5ski8PX9rL2dZXvgGDnw/1'/2)` describes a P2PKH output with child key *1'/2* of the specified xpub. - `pkh([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/1/*)` describes a set of P2PKH outputs, but additionally specifies that the specified xpub is a child of a master with fingerprint `d34db33f`, and derived using path `44'/0'/0'`. @@ -51,6 +53,7 @@ - `pkh(KEY)` (anywhere): P2PKH output for the given public key (use `addr` if you only know the pubkey hash). - `combo(KEY)` (top level only): an alias for the collection of `pk(KEY)` and `pkh(KEY)`. - `multi(k,KEY_1,KEY_2,...,KEY_n)` (anywhere): k-of-n multisig script. +- `sortedmulti(k,KEY_1,KEY_2,...,KEY_n)` (anywhere): k-of-n multisig script with keys sorted lexicographically in the resulting script. - `addr(ADDR)` (top level only): the script which ADDR expands to. - `raw(HEX)` (top level only): the script whose hex encoding is HEX. @@ -92,11 +95,12 @@ Several pieces of software use multi-signature (multisig) scripts based on Bitcoin's OP_CHECKMULTISIG opcode. To support these, we introduce the -`multi(k,key_1,key_2,...,key_n)` function. It represents a *k-of-n* +`multi(k,key_1,key_2,...,key_n)` and `sortedmulti(k,key_1,key_2,...,key_n)` +functions. They represent a *k-of-n* multisig policy, where any *k* out of the *n* provided public keys must sign. -Key order is significant. A `multi()` expression describes a multisig script +Key order is significant for `multi()`. A `multi()` expression describes a multisig script with keys in the specified order, and in a search for TXOs, it will not match outputs with multisig scriptPubKeys that have the same keys in a different order. Also, to prevent a combinatorial explosion of the search space, if more @@ -105,6 +109,10 @@ child key from each wildcard path in lockstep, rather than scripts with any combination of child keys from each wildcard path. +Key order does not matter for `sortedmulti()`. `sortedmulti()` behaves in the same way +as `multi()` does but the keys are reordered in the resulting script such that they +are lexicographically ordered as described in BIP67. + ### BIP32 derived keys and chains Most modern wallet software and hardware uses keys that are derived using diff --git a/doc/release-notes.md b/doc/release-notes.md --- a/doc/release-notes.md +++ b/doc/release-notes.md @@ -23,6 +23,9 @@ - The RPC gettransaction, listtransactions and listsinceblock responses now also includes the height of the block that contains the wallet transaction, if any. +- A new descriptor type `sortedmulti(...)` has been added to support multisig scripts + where the public keys are sorted lexicographically in the resulting script. + Deprecated or removed RPCs -------------------------- - The `getaddressinfo` RPC `labels` field now returns an array of label name diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -693,6 +693,7 @@ /** A parsed multi(...) descriptor. */ class MultisigDescriptor final : public DescriptorImpl { const int m_threshold; + const bool m_sorted; protected: std::string ToStringExtra() const override { @@ -701,14 +702,21 @@ std::vector MakeScripts(const std::vector &keys, const CScript *, FlatSigningProvider &) const override { + if (m_sorted) { + std::vector sorted_keys(keys); + std::sort(sorted_keys.begin(), sorted_keys.end()); + return Vector(GetScriptForMultisig(m_threshold, sorted_keys)); + } return Vector(GetScriptForMultisig(m_threshold, keys)); } public: MultisigDescriptor(int threshold, - std::vector> providers) - : DescriptorImpl(std::move(providers), {}, "multi"), - m_threshold(threshold) {} + std::vector> providers, + bool sorted = false) + : DescriptorImpl(std::move(providers), {}, + sorted ? "sortedmulti" : "multi"), + m_threshold(threshold), m_sorted(sorted) {} }; /** A parsed sh(...) descriptor. */ @@ -875,6 +883,7 @@ using namespace spanparsing; auto expr = Expr(sp); + bool sorted_multi = false; if (Func("pk", expr)) { auto pubkey = ParsePubkey(expr, out, error); if (!pubkey) { @@ -899,7 +908,7 @@ error = "Cannot have combo in non-top level"; return nullptr; } - if (Func("multi", expr)) { + if ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr)) { auto threshold = Expr(expr); uint32_t thres; std::vector> providers; @@ -956,8 +965,8 @@ return nullptr; } } - return std::make_unique(thres, - std::move(providers)); + return std::make_unique(thres, std::move(providers), + sorted_multi); } if (ctx == ParseScriptContext::TOP && Func("sh", expr)) { auto desc = ParseScript(expr, ParseScriptContext::P2SH, out, error); diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp --- a/src/test/descriptor_tests.cpp +++ b/src/test/descriptor_tests.cpp @@ -431,6 +431,28 @@ "c5bd4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c5" "40c5bd5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abe" "a23552ae"}}); + Check("sortedmulti(1,L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1," + "5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)", + "sortedmulti(1," + "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd," + "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b" + "8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)", + SIGNABLE, + {{"512103a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540" + "c5bd4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c5" + "40c5bd5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abe" + "a23552ae"}}); + Check("sortedmulti(1,5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss," + "L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)", + "sortedmulti(1," + "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b" + "8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235," + "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)", + SIGNABLE, + {{"512103a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540" + "c5bd4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c5" + "40c5bd5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abe" + "a23552ae"}}); Check("sh(multi(2,[00000000/111'/222]" "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39" "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc," @@ -443,6 +465,29 @@ "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))", DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}}, {{0x8000006FUL, 222}, {0}}); + Check("sortedmulti(2," + "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39" + "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc/" + "*," + "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7" + "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0/0/*)", + "sortedmulti(2," + "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4" + "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/" + "*," + "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB" + "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0/0/*)", + RANGE, + {{"5221025d5fc65ebb8d44a5274b53bac21ff8307fec2334a32df05553459f8b1f7f" + "e1b62102fbd47cc8034098f0e6a94c6aeee8528abf0a2153a5d8e46d325b7284c0" + "46784652ae"}, + {"52210264fd4d1f5dea8ded94c61e9641309349b62f27fbffe807291f664e286bfb" + "e6472103f4ece6dfccfa37b211eb3d0af4d0c61dba9ef698622dc17eecdf764bee" + "b005a652ae"}, + {"5221022ccabda84c30bad578b13c89eb3b9544ce149787e5b538175b1d1ba259cb" + "b83321024d902e1a2fc7a8755ab5b694c575fce742c48d9ff192e63df5193e4c7a" + "fe1f9c52ae"}}, + {{0}, {1}, {2}, {0, 0, 0}, {0, 0, 1}, {0, 0, 2}}); // P2SH does not fit 16 compressed pubkeys in a redeemscript CheckUnparsable( "sh(multi(16," diff --git a/test/functional/data/rpc_bip67.json b/test/functional/data/rpc_bip67.json new file mode 100644 --- /dev/null +++ b/test/functional/data/rpc_bip67.json @@ -0,0 +1,58 @@ +[ + { + "keys": [ + "02ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f8", + "02fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f" + ], + "sorted_keys": [ + "02fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f", + "02ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f8" + ], + "script": "522102fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f2102ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f852ae", + "address": "bchreg:ppttar4f8yf0xa592s4z4pj22cq03zn82s794w79cp" + }, + { + "keys": [ + "02632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0", + "027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e77", + "02e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b404" + ], + "sorted_keys": [ + "02632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0", + "027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e77", + "02e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b404" + ], + "script": "522102632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed021027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e772102e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b40453ae", + "address": "bchreg:pp6g6vlqksp4s4lwgl6pwnsdlrt090dacg9uza2swt" + }, + { + "keys": [ + "030000000000000000000000000000000000004141414141414141414141414141", + "020000000000000000000000000000000000004141414141414141414141414141", + "020000000000000000000000000000000000004141414141414141414141414140", + "030000000000000000000000000000000000004141414141414141414141414140" + ], + "sorted_keys": [ + "020000000000000000000000000000000000004141414141414141414141414140", + "020000000000000000000000000000000000004141414141414141414141414141", + "030000000000000000000000000000000000004141414141414141414141414140", + "030000000000000000000000000000000000004141414141414141414141414141" + ], + "script": "522102000000000000000000000000000000000000414141414141414141414141414021020000000000000000000000000000000000004141414141414141414141414141210300000000000000000000000000000000000041414141414141414141414141402103000000000000000000000000000000000000414141414141414141414141414154ae", + "address": "bchreg:pqyts3ju07qzsd38xlyjcj9g4gs87prdqqkfwmt89s" + }, + { + "keys": [ + "022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da", + "03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9", + "021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18" + ], + "sorted_keys": [ + "021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18", + "022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da", + "03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9" + ], + "script": "5221021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc1821022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da2103e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e953ae", + "address": "bchreg:pr6hftp4zpwlct6z9rtv8u8vpaaee5zwlvpw5j3n9e" + } +] diff --git a/test/functional/rpc_createmultisig.py b/test/functional/rpc_createmultisig.py --- a/test/functional/rpc_createmultisig.py +++ b/test/functional/rpc_createmultisig.py @@ -4,6 +4,7 @@ # file COPYING or http://www.opensource.org/licenses/mit-license.php. """Test multisig RPCs""" +from test_framework.descriptors import descsum_create from test_framework.test_framework import BitcoinTestFramework from test_framework.util import ( assert_raises_rpc_error, @@ -14,6 +15,8 @@ import binascii import decimal import itertools +import json +import os class RpcCreateMultiSigTest(BitcoinTestFramework): @@ -73,6 +76,21 @@ # legacy addresses assert_equal(legacy_addr, node0.createmultisig(2, keys)['address']) + self.log.info( + 'Testing sortedmulti descriptors with BIP 67 test vectors') + with open(os.path.join(os.path.dirname(os.path.realpath(__file__)), 'data/rpc_bip67.json'), encoding='utf-8') as f: + vectors = json.load(f) + + for t in vectors: + key_str = ','.join(t['keys']) + desc = descsum_create('sh(sortedmulti(2,{}))'.format(key_str)) + assert_equal(self.nodes[0].deriveaddresses(desc)[0], t['address']) + sorted_key_str = ','.join(t['sorted_keys']) + sorted_key_desc = descsum_create( + 'sh(multi(2,{}))'.format(sorted_key_str)) + assert_equal(self.nodes[0].deriveaddresses( + sorted_key_desc)[0], t['address']) + def check_addmultisigaddress_errors(self): self.log.info( 'Check that addmultisigaddress fails when the private keys are missing')