Merge #17056: descriptors: Introduce sortedmulti descriptor

4bb660be90a2811b53855bf1fd33a8dd9ba3db47 Add release note (Andrew Chow)
ed96b295d747738334459490c79b7360ab85aaf7 Update descriptors.md to include sortedmulti (Andrew Chow)
80be78ea75ac9833ee3db3d468ed09fc4fe6274c Test sortedmulti descriptor using BIP 67 tests (Andrew Chow)
6f588fd2276e5b713c6d36e3b01288484ddb59c0 Add sortedmulti descriptor and unit tests (Andrew Chow)

Pull request description:

  Adds a `sortedmulti()` descriptor as mentioned in https://github.com/bitcoin/bitcoin/pull/17023#issuecomment-537596416.

  `sortedmulti()` works in the same way as `multi` does but sorts the pubkeys in the resulting scripts in lexicographic order as described in [BIP67](https://github.com/bitcoin/bips/blob/master/bip-0067.mediawiki). Note that this does not add support for BIP67 nor is BIP67 fully supported by this descriptor (which is why it is not named `multi67()`) as it does not require compressed pubkeys.

  Tests from BIP67 were added and documentation was updated.

ACKs for top commit:
  instagibbs:
    re-ACK https://github.com/bitcoin/bitcoin/pull/17056/commits/4bb660be90a2811b53855bf1fd33a8dd9ba3db47
  Sjors:
    re-ACK 4bb660be90a2811b53855bf1fd33a8dd9ba3db47

Tree-SHA512: 93b21112a74ebe0bf316d8f3e0291f69fd975cf0a29332f9728e7b880cad312b8b14007e86adcd7899f117b9303cbcf4cb35f3bb2f2f648d1a446f83f75a70a5

2 files changed, 73 insertions, 0 deletions

diff --git a/test/functional/data/rpc_bip67.json b/test/functional/data/rpc_bip67.json
new file mode 100644
index 0000000000..4d6f793d4a
--- /dev/null
+++ b/test/functional/data/rpc_bip67.json
@@ -0,0 +1,58 @@
+[
+    {
+        "keys": [
+            "02ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f8",
+            "02fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f"
+        ],
+        "sorted_keys": [
+            "02fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f",
+            "02ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f8"
+        ],
+        "script": "522102fe6f0a5a297eb38c391581c4413e084773ea23954d93f7753db7dc0adc188b2f2102ff12471208c14bd580709cb2358d98975247d8765f92bc25eab3b2763ed605f852ae",
+        "address": "2N19tNw3Ss4L9QDERtCw7FhXb6jBsYmeXNu"
+    },
+    {
+        "keys": [
+            "02632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0",
+            "027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e77",
+            "02e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b404"
+        ],
+        "sorted_keys": [
+            "02632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0",
+            "027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e77",
+            "02e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b404"
+        ],
+        "script": "522102632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed021027735a29bae7780a9755fae7a1c4374c656ac6a69ea9f3697fda61bb99a4f3e772102e2cc6bd5f45edd43bebe7cb9b675f0ce9ed3efe613b177588290ad188d11b40453ae",
+        "address": "2N3sVXU7MZefmYnZhrVX2bA7LyH6vygFZZ7"
+    },
+    {
+        "keys": [
+            "030000000000000000000000000000000000004141414141414141414141414141",
+            "020000000000000000000000000000000000004141414141414141414141414141",
+            "020000000000000000000000000000000000004141414141414141414141414140",
+            "030000000000000000000000000000000000004141414141414141414141414140"
+        ],
+        "sorted_keys": [
+            "020000000000000000000000000000000000004141414141414141414141414140",
+            "020000000000000000000000000000000000004141414141414141414141414141",
+            "030000000000000000000000000000000000004141414141414141414141414140",
+            "030000000000000000000000000000000000004141414141414141414141414141"
+        ],
+        "script": "522102000000000000000000000000000000000000414141414141414141414141414021020000000000000000000000000000000000004141414141414141414141414141210300000000000000000000000000000000000041414141414141414141414141402103000000000000000000000000000000000000414141414141414141414141414154ae",
+        "address": "2Mt3L9TcDUAfLpSoyB3SNYtJGLiU49DKEWJ"
+    },
+    {
+        "keys": [
+            "022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da",
+            "03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9",
+            "021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18"
+        ],
+        "sorted_keys": [
+            "021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18",
+            "022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da",
+            "03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9"
+        ],
+        "script": "5221021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc1821022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da2103e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e953ae",
+        "address": "2NFd5JqpwmQNz3gevZJ3rz9ofuHvqaP9Cye"
+    }
+]
diff --git a/test/functional/rpc_createmultisig.py b/test/functional/rpc_createmultisig.py
index 056e193d55..2a64a29967 100755
--- 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 @@ from test_framework.key import ECPubKey
 import binascii
 import decimal
 import itertools
+import json
+import os
 
 class RpcCreateMultiSigTest(BitcoinTestFramework):
     def set_test_params(self):
@@ -72,6 +75,18 @@ class RpcCreateMultiSigTest(BitcoinTestFramework):
             assert_equal(legacy_addr, node0.addmultisigaddress(2, keys, '', 'bech32')['address'])
             assert_equal(legacy_addr, node0.addmultisigaddress(2, keys, '', 'p2sh-segwit')['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')
         addresses = [self.nodes[1].getnewaddress(address_type='legacy') for _ in range(2)]