bitcoin · afk11 · Nov 8, 2016 · Feb 4, 2017 · Feb 4, 2017 · Sep 30, 2017
diff --git a/doc/bips.md b/doc/bips.md
@@ -18,6 +18,7 @@ BIPs that are implemented by Bitcoin Core (up-to-date up to **v0.13.0**):
 * [`BIP 61`](https://github.com/bitcoin/bips/blob/master/bip-0061.mediawiki): The 'reject' protocol message (and the protocol version bump to 70002) was added in **v0.9.0** ([PR #3185](https://github.com/bitcoin/bitcoin/pull/3185)).
 * [`BIP 65`](https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki): The CHECKLOCKTIMEVERIFY softfork was merged in **v0.12.0** ([PR #6351](https://github.com/bitcoin/bitcoin/pull/6351)), and backported to **v0.11.2** and **v0.10.4**. Mempool-only CLTV was added in [PR #6124](https://github.com/bitcoin/bitcoin/pull/6124).
 * [`BIP 66`](https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki): The strict DER rules and associated version 3 blocks have been implemented since **v0.10.0** ([PR #5713](https://github.com/bitcoin/bitcoin/pull/5713)).
+* [`BIP 67`](https://github.com/bitcoin/bips/blob/master/bip-0067.mediawiki): Sorting multisig keys according to BIP 67 was merged in **v0.15.1** ([PR #8751](https://github.com/bitcoin/bitcoin/pull/8751)).
 * [`BIP 68`](https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki): Sequence locks have been implemented as of **v0.12.1**  ([PR #7184](https://github.com/bitcoin/bitcoin/pull/7184)), and have been activated since *block 419328*.
 * [`BIP 70`](https://github.com/bitcoin/bips/blob/master/bip-0070.mediawiki) [`71`](https://github.com/bitcoin/bips/blob/master/bip-0071.mediawiki) [`72`](https://github.com/bitcoin/bips/blob/master/bip-0072.mediawiki): Payment Protocol support has been available in Bitcoin Core GUI since **v0.9.0** ([PR #5216](https://github.com/bitcoin/bitcoin/pull/5216)).
 * [`BIP 90`](https://github.com/bitcoin/bips/blob/master/bip-0090.mediawiki): Trigger mechanism for activation of BIPs 34, 65, and 66 has been simplified to block height checks since **v0.14.0** ([PR #8391](https://github.com/bitcoin/bitcoin/pull/8391)).

diff --git a/src/rpc/client.cpp b/src/rpc/client.cpp
@@ -76,8 +76,10 @@ static const CRPCConvertParam vRPCConvertParams[] =
     { "sendmany", 6 , "conf_target" },
     { "addmultisigaddress", 0, "nrequired" },
     { "addmultisigaddress", 1, "keys" },
+    { "addmultisigaddress", 3, "sort" },
     { "createmultisig", 0, "nrequired" },
     { "createmultisig", 1, "keys" },
+    { "createmultisig", 2, "sort" },
     { "listunspent", 0, "minconf" },
     { "listunspent", 1, "maxconf" },
     { "listunspent", 2, "addresses" },

diff --git a/src/rpc/misc.cpp b/src/rpc/misc.cpp
@@ -212,7 +212,7 @@ class CWallet;
 /**
  * Used by addmultisigaddress / createmultisig:
  */
-CScript _createmultisig_redeemScript(CWallet * const pwallet, const UniValue& params)
+CScript _createmultisig_redeemScript(CWallet * const pwallet, const UniValue& params, bool fSorted)
 {
     int nRequired = params[0].get_int();
     const UniValue& keys = params[1].get_array();
@@ -245,6 +245,8 @@ CScript _createmultisig_redeemScript(CWallet * const pwallet, const UniValue& pa
             }
             if (!vchPubKey.IsFullyValid())
                 throw std::runtime_error(" Invalid public key: "+ks);
+            if (fSorted && !vchPubKey.IsCompressed())
+                throw std::runtime_error(" Compressed key required for BIP67: "+ks);
             pubkeys[i] = vchPubKey;
         }
 
@@ -256,14 +258,16 @@ CScript _createmultisig_redeemScript(CWallet * const pwallet, const UniValue& pa
             CPubKey vchPubKey(ParseHex(ks));
             if (!vchPubKey.IsFullyValid())
                 throw std::runtime_error(" Invalid public key: "+ks);
+            if (fSorted && !vchPubKey.IsCompressed())
+                throw std::runtime_error(" Compressed key required for BIP67: "+ks);
             pubkeys[i] = vchPubKey;
         }
         else
         {
             throw std::runtime_error(" Invalid public key: "+ks);
         }
     }
-    CScript result = GetScriptForMultisig(nRequired, pubkeys);
+    CScript result = GetScriptForMultisig(nRequired, pubkeys, fSorted);
 
     if (result.size() > MAX_SCRIPT_ELEMENT_SIZE)
         throw std::runtime_error(
@@ -280,11 +284,12 @@ UniValue createmultisig(const JSONRPCRequest& request)
     CWallet * const pwallet = nullptr;
 #endif
 
-    if (request.fHelp || request.params.size() < 2 || request.params.size() > 2)
+    if (request.fHelp || request.params.size() < 2 || request.params.size() > 3)
     {
-        std::string msg = "createmultisig nrequired [\"key\",...]\n"
+        std::string msg = "createmultisig nrequired [\"key\",...] ( sort )\n"
             "\nCreates a multi-signature address with n signature of m keys required.\n"
             "It returns a json object with the address and redeemScript.\n"
+            "Public keys can be sorted according to BIP67 during the request if required.\n"
 
             "\nArguments:\n"
             "1. nrequired      (numeric, required) The number of required signatures out of the n keys or addresses.\n"
@@ -293,6 +298,7 @@ UniValue createmultisig(const JSONRPCRequest& request)
             "       \"key\"    (string) bitcoin address or hex-encoded public key\n"
             "       ,...\n"
             "     ]\n"
+            "3. sort           (bool, optional) Whether to sort public keys according to BIP67. Default setting is false.\n"
 
             "\nResult:\n"
             "{\n"
@@ -309,8 +315,10 @@ UniValue createmultisig(const JSONRPCRequest& request)
         throw std::runtime_error(msg);
     }
 
+    bool fSorted = request.params.size() > 2 && request.params[2].get_bool();
+
     // Construct using pay-to-script-hash:
-    CScript inner = _createmultisig_redeemScript(pwallet, request.params);
+    CScript inner = _createmultisig_redeemScript(pwallet, request.params, fSorted);
     CScriptID innerID(inner);
 
     UniValue result(UniValue::VOBJ);
@@ -629,7 +637,7 @@ static const CRPCCommand commands[] =
     { "control",            "getmemoryinfo",          &getmemoryinfo,          {"mode"} },
     { "control",            "logging",                &logging,                {"include", "exclude"}},
     { "util",               "validateaddress",        &validateaddress,        {"address"} }, /* uses wallet if enabled */
-    { "util",               "createmultisig",         &createmultisig,         {"nrequired","keys"} },
+    { "util",               "createmultisig",         &createmultisig,         {"nrequired","keys","sort"} },
     { "util",               "verifymessage",          &verifymessage,          {"address","signature","message"} },
     { "util",               "signmessagewithprivkey", &signmessagewithprivkey, {"privkey","message"} },
 

diff --git a/src/script/standard.cpp b/src/script/standard.cpp
@@ -329,13 +329,23 @@ CScript GetScriptForRawPubKey(const CPubKey& pubKey)
     return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
 }
 
-CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
+CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys, bool fSorted)
 {
-    CScript script;
+    std::vector<std::vector<unsigned char>> vEncoded;
+    vEncoded.reserve(keys.size());
+    for (const CPubKey& key : keys) {
+        vEncoded.emplace_back(ToByteVector(key));
+    }
+
+    if (fSorted) {
+        std::sort(vEncoded.begin(), vEncoded.end());
+    }
 
+    CScript script;
     script << CScript::EncodeOP_N(nRequired);
-    for (const CPubKey& key : keys)
-        script << ToByteVector(key);
+    for (std::vector<unsigned char> bytes : vEncoded) {
+        script << bytes;
+    }
     script << CScript::EncodeOP_N(keys.size()) << OP_CHECKMULTISIG;
     return script;
 }

diff --git a/src/script/standard.h b/src/script/standard.h
@@ -158,7 +158,7 @@ CScript GetScriptForDestination(const CTxDestination& dest);
 CScript GetScriptForRawPubKey(const CPubKey& pubkey);
 
 /** Generate a multisig script. */
-CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys);
+CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys, bool fSorted=false);
 
 /**
  * Generate a pay-to-witness script for the given redeem script. If the redeem

diff --git a/src/wallet/rpcwallet.cpp b/src/wallet/rpcwallet.cpp
@@ -1139,7 +1139,7 @@ UniValue sendmany(const JSONRPCRequest& request)
 }
 
 // Defined in rpc/misc.cpp
-extern CScript _createmultisig_redeemScript(CWallet * const pwallet, const UniValue& params);
+extern CScript _createmultisig_redeemScript(CWallet * const pwallet, const UniValue& params, bool fSorted);
 
 UniValue addmultisigaddress(const JSONRPCRequest& request)
 {
@@ -1148,21 +1148,24 @@ UniValue addmultisigaddress(const JSONRPCRequest& request)
         return NullUniValue;
     }
 
-    if (request.fHelp || request.params.size() < 2 || request.params.size() > 3)
+    if (request.fHelp || request.params.size() < 2 || request.params.size() > 4)
     {
-        std::string msg = "addmultisigaddress nrequired [\"key\",...] ( \"account\" )\n"
+        std::string msg = "addmultisigaddress nrequired [\"key\",...] ( \"account\" ) ( sort )\n"
             "\nAdd a nrequired-to-sign multisignature address to the wallet. Requires a new wallet backup.\n"
+
             "Each key is a Bitcoin address or hex-encoded public key.\n"
             "If 'account' is specified (DEPRECATED), assign address to that account.\n"
+            "Public keys can be sorted according to BIP67 during the request if required.\n"
 
             "\nArguments:\n"
-            "1. nrequired        (numeric, required) The number of required signatures out of the n keys or addresses.\n"
+            "1. nrequired      (numeric, required) The number of required signatures out of the n keys or addresses.\n"
             "2. \"keys\"         (string, required) A json array of bitcoin addresses or hex-encoded public keys\n"
             "     [\n"
             "       \"address\"  (string) bitcoin address or hex-encoded public key\n"
             "       ...,\n"
             "     ]\n"
             "3. \"account\"      (string, optional) DEPRECATED. An account to assign the addresses to.\n"
+            "4. sort           (bool, optional) Whether to sort public keys according to BIP67. Default setting is false.\n"
 
             "\nResult:\n"
             "\"address\"         (string) A bitcoin address associated with the keys.\n"
@@ -1182,8 +1185,10 @@ UniValue addmultisigaddress(const JSONRPCRequest& request)
     if (!request.params[2].isNull())
         strAccount = AccountFromValue(request.params[2]);
 
+    bool fSorted = request.params.size() > 3 && request.params[3].get_bool();
+
     // Construct using pay-to-script-hash:
-    CScript inner = _createmultisig_redeemScript(pwallet, request.params);
+    CScript inner = _createmultisig_redeemScript(pwallet, request.params, fSorted);
     CScriptID innerID(inner);
     pwallet->AddCScript(inner);
 
@@ -3445,7 +3450,7 @@ static const CRPCCommand commands[] =
     { "hidden",             "resendwallettransactions", &resendwallettransactions, {} },
     { "wallet",             "abandontransaction",       &abandontransaction,       {"txid"} },
     { "wallet",             "abortrescan",              &abortrescan,              {} },
-    { "wallet",             "addmultisigaddress",       &addmultisigaddress,       {"nrequired","keys","account"} },
+    { "wallet",             "addmultisigaddress",       &addmultisigaddress,       {"nrequired","keys","account","sort"} },
     { "wallet",             "addwitnessaddress",        &addwitnessaddress,        {"address","p2sh"} },
     { "wallet",             "backupwallet",             &backupwallet,             {"destination"} },
     { "wallet",             "bumpfee",                  &bumpfee,                  {"txid", "options"} },

diff --git a/test/functional/sort_multisig.py b/test/functional/sort_multisig.py
@@ -0,0 +1,83 @@
+#!/usr/bin/env python3
+# Copyright (c) 2014-2016 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+# Exercise the createmultisig API
+
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import *
+
+class SortMultisigTest(BitcoinTestFramework):
+    def set_test_params(self):
+        self.num_nodes = 1
+        self.extra_args = [[]]
+        self.setup_clean_chain = True
+
+    def run_simple_test(self):
+        pub1 = "022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da"
+        pub2 = "03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9"
+        pub3 = "021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18"
+
+        pubs = [pub1,pub2,pub3]
+
+        default = self.nodes[0].createmultisig(2, pubs)
+        unsorted = self.nodes[0].createmultisig(2, pubs, False)
+
+        assert_equal("2N2BchzwfyuqJep7sKmFfBucfopHZQuPnpt", unsorted["address"])
+        assert_equal("5221022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da2103e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e921021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc1853ae", unsorted["redeemScript"])
+        assert_equal(default["address"], unsorted["address"])
+        assert_equal(default["redeemScript"], unsorted["redeemScript"])
+
+        sorted = self.nodes[0].createmultisig(2, pubs, True)
+        assert_equal("2NFd5JqpwmQNz3gevZJ3rz9ofuHvqaP9Cye", sorted["address"])
+        assert_equal("5221021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc1821022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da2103e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e953ae", sorted["redeemScript"])
+
+    def run_demonstrate_sorting(self):
+        pub1 = "022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da"
+        pub2 = "03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9"
+        pub3 = "021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18"
+
+        sorted = self.nodes[0].createmultisig(2, [pub3,pub1,pub2,])
+
+        self.test_if_result_matches(2, [pub1,pub2,pub3], True, sorted["address"])
+        self.test_if_result_matches(2, [pub1,pub3,pub2], True, sorted["address"])
+        self.test_if_result_matches(2, [pub2,pub3,pub1], True, sorted["address"])
+        self.test_if_result_matches(2, [pub2,pub1,pub3], True, sorted["address"])
+        self.test_if_result_matches(2, [pub3,pub1,pub2], True, sorted["address"])
+        self.test_if_result_matches(2, [pub3,pub2,pub1], True, sorted["address"])
+
+        self.test_if_result_matches(2, [pub1,pub2,pub3], False, sorted["address"])
+        self.test_if_result_matches(2, [pub1,pub3,pub2], False, sorted["address"])
+        self.test_if_result_matches(2, [pub2,pub3,pub1], False, sorted["address"])
+        self.test_if_result_matches(2, [pub2,pub1,pub3], False, sorted["address"])
+        self.test_if_result_matches(2, [pub3,pub2,pub1], False, sorted["address"])
+
+    def test_if_result_matches(self, m, keys, sort, against):
+        result = self.nodes[0].createmultisig(m, keys, sort)
+        assert_equal(sort, result["address"] == against)
+
+    def test_compressed_keys_forbidden(self):
+        pub1 = "02fdf7e1b65a477a7815effde996a03a7d94cbc46f7d14c05ef38425156fc92e22"
+        pub2 = "04823336da95f0b4cf745839dff26992cef239ad2f08f494e5b57c209e4f3602d5526bc251d480e3284d129f736441560e17f3a7eb7ed665fdf0158f44550b926c"
+        rs = "522102fdf7e1b65a477a7815effde996a03a7d94cbc46f7d14c05ef38425156fc92e224104823336da95f0b4cf745839dff26992cef239ad2f08f494e5b57c209e4f3602d5526bc251d480e3284d129f736441560e17f3a7eb7ed665fdf0158f44550b926c52ae"
+        pubs = [pub1,pub2]
+
+        default = self.nodes[0].createmultisig(2, pubs)
+        assert_equal(rs, default["redeemScript"])
+
+        unsorted = self.nodes[0].createmultisig(2, pubs, False)
+        assert_equal(rs, unsorted["redeemScript"])
+        assert_equal(default["address"], unsorted["address"])
+        assert_equal(default["redeemScript"], unsorted["redeemScript"])
+
+        assert_raises_rpc_error(-1, "Compressed key required for BIP67: 04823336da95f0b4cf745839dff26992cef239ad2f08f494e5b57c209e4f3602d5526bc251d480e3284d129f736441560e17f3a7eb7ed665fdf0158f44550b926c", self.nodes[0].createmultisig, 2, pubs, True)
+
+    def run_test(self):
+        self.run_simple_test()
+        self.run_demonstrate_sorting()
+        self.test_compressed_keys_forbidden()
+
+if __name__ == '__main__':
+    SortMultisigTest().main()
+
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
@@ -112,6 +112,7 @@
     'importprunedfunds.py',
     'signmessages.py',
     'nulldummy.py',
+    'sort_multisig.py',
     'import-rescan.py',
     'mining.py',
     'bumpfee.py',

diff --git a/test/functional/wallet-accounts.py b/test/functional/wallet-accounts.py
@@ -14,15 +14,51 @@
 """
 
 from test_framework.test_framework import BitcoinTestFramework
-from test_framework.util import assert_equal
+from test_framework.util import assert_equal, assert_raises_rpc_error
 
 class WalletAccountsTest(BitcoinTestFramework):
     def set_test_params(self):
         self.setup_clean_chain = True
         self.num_nodes = 1
-        self.extra_args = [[]]
+        self.extra_args = [["-maxorphantx=1000", "-whitelist=127.0.0.1"]]
 
-    def run_test(self):
+    def test_sort_multisig(self, node):
+        node.importprivkey("cSJUMwramrFYHKPfY77FH94bv4Q5rwUCyfD6zX3kLro4ZcWsXFEM")
+        node.importprivkey("cSpQbSsdKRmxaSWJ3TckCFTrksXNPbh8tfeZESGNQekkVxMbQ77H")
+        node.importprivkey("cRNbfcJgnvk2QJEVbMsxzoprotm1cy3kVA2HoyjSs3ss5NY5mQqr")
+
+        addresses = [
+            "muRmfCwue81ZT9oc3NaepefPscUHtP5kyC",
+            "n12RzKwqWPPA4cWGzkiebiM7Gu6NXUnDW8",
+            "n2yWMtx8jVbo8wv9BK2eN1LdbaakgKL3Mt",
+        ]
+
+        sorted_default = node.addmultisigaddress(2, addresses, "sort-test")
+        sorted_false = node.addmultisigaddress(2, addresses, "sort-test", False)
+        sorted_true = node.addmultisigaddress(2, addresses, "sort-test", True)
+
+        assert_equal(sorted_default, sorted_false)
+        assert_equal("2N6dne8yzh13wsRJxCcMgCYNeN9fxKWNHt8", sorted_default)
+        assert_equal("2MsJ2YhGewgDPGEQk4vahGs4wRikJXpRRtU", sorted_true)
+
+    def test_sort_multisig_with_uncompressed_hash160(self, node):
+        node.importpubkey("02632b12f4ac5b1d1b72b2a3b508c19172de44f6f46bcee50ba33f3f9291e47ed0")
+        node.importpubkey("04dd4fe618a8ad14732f8172fe7c9c5e76dd18c2cc501ef7f86e0f4e285ca8b8b32d93df2f4323ebb02640fa6b975b2e63ab3c9d6979bc291193841332442cc6ad")
+        address = "2MxvEpFdXeEDbnz8MbRwS23kDZC8tzQ9NjK"
+
+        addresses = [
+            "msDoRfEfZQFaQNfAEWyqf69H99yntZoBbG",
+            "myrfasv56W7579LpepuRy7KFhVhaWsJYS8",
+        ]
+        default = self.nodes[0].addmultisigaddress(2, addresses)
+        assert_equal(address, default)
+
+        unsorted = self.nodes[0].addmultisigaddress(2, addresses, "", False)
+        assert_equal(address, unsorted)
+
+        assert_raises_rpc_error(-1, "Compressed key required for BIP67: myrfasv56W7579LpepuRy7KFhVhaWsJYS8", node.addmultisigaddress, 2, addresses, "", True)
+
+    def run_test (self):
         node = self.nodes[0]
         # Check that there's no UTXO on any of the nodes
         assert_equal(len(node.listunspent()), 0)
@@ -134,6 +170,9 @@ def run_test(self):
         for account in accounts:
             assert_equal(node.getbalance(account.name), 50)
 
+        self.test_sort_multisig(node)
+        self.test_sort_multisig_with_uncompressed_hash160(node)
+
         # Check that setaccount can change the account of an address from a
         # different account.
         change_account(node, accounts[0].addresses[0], accounts[0], accounts[1])
@@ -201,6 +240,5 @@ def change_account(node, address, old_account, new_account):
     old_account.verify(node)
     new_account.verify(node)
 
-
 if __name__ == '__main__':
     WalletAccountsTest().main()