Support 3 new multisignature IsStandard transactions

Initial support for (a and b), (a or b), and 2-of-3 escrow
transactions (where a, b, and c are keys).

5 files changed, 575 insertions, 88 deletions

diff --git a/src/bitcoinrpc.cpp b/src/bitcoinrpc.cpp
index 1f05fa8628..122bf61b8f 100644
--- a/src/bitcoinrpc.cpp
+++ b/src/bitcoinrpc.cpp
@@ -936,6 +936,101 @@ Value sendmany(const Array& params, bool fHelp)
     return wtx.GetHash().GetHex();
 }
 
+Value sendmultisig(const Array& params, bool fHelp)
+{
+    if (fHelp || params.size() < 4 || params.size() > 7)
+    {
+        string msg = "sendmultisig <fromaccount> <type> <[\"key\",\"key\"]> <amount> [minconf=1] [comment] [comment-to]\n"
+            "<type> is one of: \"and\", \"or\", \"escrow\"\n"
+            "<keys> is an array of strings (in JSON array format); each key is a bitcoin address, hex or base58 public key\n"
+            "<amount> is a real and is rounded to the nearest 0.00000001";
+        if (pwalletMain->IsCrypted())
+            msg += "\nrequires wallet passphrase to be set with walletpassphrase first";
+        throw runtime_error(msg);
+    }
+
+    string strAccount = AccountFromValue(params[0]);
+    string strType = params[1].get_str();
+    const Array& keys = params[2].get_array();
+    int64 nAmount = AmountFromValue(params[3]);
+    int nMinDepth = 1;
+    if (params.size() > 4)
+        nMinDepth = params[4].get_int();
+
+    CWalletTx wtx;
+    wtx.strFromAccount = strAccount;
+    if (params.size() > 5 && params[5].type() != null_type && !params[5].get_str().empty())
+        wtx.mapValue["comment"] = params[5].get_str();
+    if (params.size() > 6 && params[6].type() != null_type && !params[6].get_str().empty())
+        wtx.mapValue["to"]      = params[6].get_str();
+
+    if (pwalletMain->IsLocked())
+        throw JSONRPCError(-13, "Error: Please enter the wallet passphrase with walletpassphrase first.");
+
+    // Check funds
+    int64 nBalance = GetAccountBalance(strAccount, nMinDepth);
+    if (nAmount > nBalance)
+        throw JSONRPCError(-6, "Account has insufficient funds");
+
+    // Gather public keys
+    int nKeysNeeded = 0;
+    if (strType == "and" || strType == "or")
+        nKeysNeeded = 2;
+    else if (strType == "escrow")
+        nKeysNeeded = 3;
+    else
+        throw runtime_error("sendmultisig: <type> must be one of: and or and_or");
+    if (keys.size() != nKeysNeeded)
+        throw runtime_error(
+            strprintf("sendmultisig: wrong number of keys (got %d, need %d)", keys.size(), nKeysNeeded));
+    std::vector<CKey> pubkeys;
+    pubkeys.resize(nKeysNeeded);
+    for (int i = 0; i < nKeysNeeded; i++)
+    {
+        const std::string& ks = keys[i].get_str();
+        if (ks.size() == 130) // hex public key
+            pubkeys[i].SetPubKey(ParseHex(ks));
+        else if (ks.size() > 34) // base58-encoded
+        {
+            std::vector<unsigned char> vchPubKey;
+            if (DecodeBase58(ks, vchPubKey))
+                pubkeys[i].SetPubKey(vchPubKey);
+            else
+                throw runtime_error("Error base58 decoding key: "+ks);
+        }
+        else // bitcoin address for key in this wallet
+        {
+            CBitcoinAddress address(ks);
+            if (!pwalletMain->GetKey(address, pubkeys[i]))
+                throw runtime_error(
+                    strprintf("sendmultisig: unknown address: %s",ks.c_str()));
+        }
+    }
+
+    // Send
+    CScript scriptPubKey;
+    if (strType == "and")
+        scriptPubKey.SetMultisigAnd(pubkeys);
+    else if (strType == "or")
+        scriptPubKey.SetMultisigOr(pubkeys);
+    else
+        scriptPubKey.SetMultisigEscrow(pubkeys);
+
+    CReserveKey keyChange(pwalletMain);
+    int64 nFeeRequired = 0;
+    bool fCreated = pwalletMain->CreateTransaction(scriptPubKey, nAmount, wtx, keyChange, nFeeRequired);
+    if (!fCreated)
+    {
+        if (nAmount + nFeeRequired > pwalletMain->GetBalance())
+            throw JSONRPCError(-6, "Insufficient funds");
+        throw JSONRPCError(-4, "Transaction creation failed");
+    }
+    if (!pwalletMain->CommitTransaction(wtx, keyChange))
+        throw JSONRPCError(-4, "Transaction commit failed");
+
+    return wtx.GetHash().GetHex();
+}
+
 
 struct tallyitem
 {
@@ -1596,7 +1691,17 @@ Value validateaddress(const Array& params, bool fHelp)
         // version of the address:
         string currentAddress = address.ToString();
         ret.push_back(Pair("address", currentAddress));
-        ret.push_back(Pair("ismine", (pwalletMain->HaveKey(address) > 0)));
+        if (pwalletMain->HaveKey(address))
+        {
+            ret.push_back(Pair("ismine", true));
+            std::vector<unsigned char> vchPubKey;
+            pwalletMain->GetPubKey(address, vchPubKey);
+            ret.push_back(Pair("pubkey", HexStr(vchPubKey)));
+            std::string strPubKey(vchPubKey.begin(), vchPubKey.end());
+            ret.push_back(Pair("pubkey58", EncodeBase58(vchPubKey)));
+        }
+        else
+            ret.push_back(Pair("ismine", false));
         if (pwalletMain->mapAddressBook.count(address))
             ret.push_back(Pair("account", pwalletMain->mapAddressBook[address]));
     }
@@ -1841,6 +1946,7 @@ pair<string, rpcfn_type> pCallTable[] =
     make_pair("move",                   &movecmd),
     make_pair("sendfrom",               &sendfrom),
     make_pair("sendmany",               &sendmany),
+    make_pair("sendmultisig",           &sendmultisig),
     make_pair("gettransaction",         &gettransaction),
     make_pair("listtransactions",       &listtransactions),
     make_pair("signmessage",            &signmessage),
@@ -2484,6 +2590,16 @@ int CommandLineRPC(int argc, char *argv[])
             params[1] = v.get_obj();
         }
         if (strMethod == "sendmany"                && n > 2) ConvertTo<boost::int64_t>(params[2]);
+        if (strMethod == "sendmultisig"            && n > 2)
+        {
+            string s = params[2].get_str();
+            Value v;
+            if (!read_string(s, v) || v.type() != array_type)
+                throw runtime_error("sendmultisig: type mismatch "+s);
+            params[2] = v.get_array();
+        }
+        if (strMethod == "sendmultisig"            && n > 3) ConvertTo<double>(params[3]);
+        if (strMethod == "sendmultisig"            && n > 4) ConvertTo<boost::int64_t>(params[4]);
 
         // Execute
         Object reply = CallRPC(strMethod, params);
diff --git a/src/script.cpp b/src/script.cpp
index 4b2dc9a1a6..6a7913b0d5 100644
--- a/src/script.cpp
+++ b/src/script.cpp
@@ -963,8 +963,11 @@ bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CSc
 
 
 
-
-bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSolutionRet)
+//
+// Returns lists of public keys (or public key hashes), any one of which can
+// satisfy scriptPubKey
+//
+bool Solver(const CScript& scriptPubKey, vector<vector<pair<opcodetype, valtype> > >& vSolutionsRet)
 {
     // Templates
     static vector<CScript> vTemplates;
@@ -975,13 +978,24 @@ bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSo
 
         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
         vTemplates.push_back(CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG);
+
+        // Sender provides two pubkeys, receivers provides two signatures
+        vTemplates.push_back(CScript() << OP_2 << OP_PUBKEY << OP_PUBKEY << OP_2 << OP_CHECKMULTISIG);
+
+        // Sender provides two pubkeys, receivers provides one of two signatures
+        vTemplates.push_back(CScript() << OP_1 << OP_PUBKEY << OP_PUBKEY << OP_2 << OP_CHECKMULTISIG);
+
+        // Sender provides three pubkeys, receiver provides 2 of 3 signatures.
+        vTemplates.push_back(CScript() << OP_2 << OP_PUBKEY << OP_PUBKEY << OP_PUBKEY << OP_3 << OP_CHECKMULTISIG);
     }
 
     // Scan templates
     const CScript& script1 = scriptPubKey;
     BOOST_FOREACH(const CScript& script2, vTemplates)
     {
-        vSolutionRet.clear();
+        vSolutionsRet.clear();
+
+        vector<pair<opcodetype, valtype> > currentSolution;
         opcodetype opcode1, opcode2;
         vector<unsigned char> vch1, vch2;
 
@@ -992,9 +1006,7 @@ bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSo
         {
             if (pc1 == script1.end() && pc2 == script2.end())
             {
-                // Found a match
-                reverse(vSolutionRet.begin(), vSolutionRet.end());
-                return true;
+                return !vSolutionsRet.empty();
             }
             if (!script1.GetOp(pc1, opcode1, vch1))
                 break;
@@ -1004,13 +1016,54 @@ bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSo
             {
                 if (vch1.size() < 33 || vch1.size() > 120)
                     break;
-                vSolutionRet.push_back(make_pair(opcode2, vch1));
+                currentSolution.push_back(make_pair(opcode2, vch1));
             }
             else if (opcode2 == OP_PUBKEYHASH)
             {
                 if (vch1.size() != sizeof(uint160))
                     break;
-                vSolutionRet.push_back(make_pair(opcode2, vch1));
+                currentSolution.push_back(make_pair(opcode2, vch1));
+            }
+            else if (opcode2 == OP_CHECKSIG)
+            {
+                vSolutionsRet.push_back(currentSolution);
+                currentSolution.clear();
+            }
+            else if (opcode2 == OP_CHECKMULTISIG)
+            {   // Dig out the "m" from before the pubkeys:
+                CScript::const_iterator it = script2.begin();
+                opcodetype op_m;
+                script2.GetOp(it, op_m, vch1);
+                int m = CScript::DecodeOP_N(op_m);
+                int n = currentSolution.size();
+
+                if (m == 2 && n == 2)
+                {
+                    vSolutionsRet.push_back(currentSolution);
+                    currentSolution.clear();
+                }
+                else if (m == 1 && n == 2)
+                { // 2 solutions: either first key or second
+                    for (int i = 0; i < 2; i++)
+                    {
+                        vector<pair<opcodetype, valtype> > s;
+                        s.push_back(currentSolution[i]);
+                        vSolutionsRet.push_back(s);
+                    }
+                    currentSolution.clear();
+                }
+                else if (m == 2 && n == 3)
+                { // 3 solutions: any pair
+                    for (int i = 0; i < 2; i++)
+                        for (int j = i+1; j < 3; j++)
+                        {
+                            vector<pair<opcodetype, valtype> > s;
+                            s.push_back(currentSolution[i]);
+                            s.push_back(currentSolution[j]);
+                            vSolutionsRet.push_back(s);
+                        }
+                    currentSolution.clear();
+                }
             }
             else if (opcode1 != opcode2 || vch1 != vch2)
             {
@@ -1019,7 +1072,7 @@ bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSo
         }
     }
 
-    vSolutionRet.clear();
+    vSolutionsRet.clear();
     return false;
 }
 
@@ -1028,51 +1081,61 @@ bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash
 {
     scriptSigRet.clear();
 
-    vector<pair<opcodetype, valtype> > vSolution;
-    if (!Solver(scriptPubKey, vSolution))
+    vector<vector<pair<opcodetype, valtype> > > vSolutions;
+    if (!Solver(scriptPubKey, vSolutions))
         return false;
 
-    // Compile solution
-    BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
+    // See if we have all the keys for any of the solutions:
+    int whichSolution = -1;
+    for (int i = 0; i < vSolutions.size(); i++)
     {
-        if (item.first == OP_PUBKEY)
+        int keysFound = 0;
+        CScript scriptSig;
+
+        BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolutions[i])
         {
-            // Sign
-            const valtype& vchPubKey = item.second;
-            CKey key;
-            if (!keystore.GetKey(Hash160(vchPubKey), key))
-                return false;
-            if (key.GetPubKey() != vchPubKey)
-                return false;
-            if (hash != 0)
+            if (item.first == OP_PUBKEY)
             {
+                const valtype& vchPubKey = item.second;
+                CKey key;
                 vector<unsigned char> vchSig;
-                if (!key.Sign(hash, vchSig))
-                    return false;
-                vchSig.push_back((unsigned char)nHashType);
-                scriptSigRet << vchSig;
+                if (keystore.GetKey(Hash160(vchPubKey), key) && key.GetPubKey() == vchPubKey
+                    && hash != 0 && key.Sign(hash, vchSig))
+                {
+                    vchSig.push_back((unsigned char)nHashType);
+                    scriptSig << vchSig;
+                    ++keysFound;
+                }
             }
-        }
-        else if (item.first == OP_PUBKEYHASH)
-        {
-            // Sign and give pubkey
-            CKey key;
-            if (!keystore.GetKey(uint160(item.second), key))
-                return false;
-            if (hash != 0)
+            else if (item.first == OP_PUBKEYHASH)
             {
+                CKey key;
                 vector<unsigned char> vchSig;
-                if (!key.Sign(hash, vchSig))
-                    return false;
-                vchSig.push_back((unsigned char)nHashType);
-                scriptSigRet << vchSig << key.GetPubKey();
+                if (keystore.GetKey(uint160(item.second), key) 
+                    && hash != 0 && key.Sign(hash, vchSig))
+                {
+                    vchSig.push_back((unsigned char)nHashType);
+                    scriptSig << vchSig << key.GetPubKey();
+                    ++keysFound;
+                }
             }
         }
-        else
+        if (keysFound == vSolutions[i].size())
         {
-            return false;
+            whichSolution = i;
+            scriptSigRet = scriptSig;
+            break;
         }
     }
+    if (whichSolution == -1)
+        return false;
+
+    // CHECKMULTISIG bug workaround:
+    if (vSolutions.size() != 1 ||
+        vSolutions[0].size() != 1)
+    {
+        scriptSigRet.insert(scriptSigRet.begin(), OP_0);
+    }
 
     return true;
 }
@@ -1080,51 +1143,59 @@ bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash
 
 bool IsStandard(const CScript& scriptPubKey)
 {
-    vector<pair<opcodetype, valtype> > vSolution;
-    return Solver(scriptPubKey, vSolution);
+    vector<vector<pair<opcodetype, valtype> > > vSolutions;
+    return Solver(scriptPubKey, vSolutions);
 }
 
 
 bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey)
 {
-    vector<pair<opcodetype, valtype> > vSolution;
-    if (!Solver(scriptPubKey, vSolution))
+    vector<vector<pair<opcodetype, valtype> > > vSolutions;
+    if (!Solver(scriptPubKey, vSolutions))
         return false;
 
-    // Compile solution
-    BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
+    int keysFound = 0;
+    int keysRequired = 0;
+    for (int i = 0; i < vSolutions.size(); i++)
     {
-        if (item.first == OP_PUBKEY)
-        {
-            const valtype& vchPubKey = item.second;
-            vector<unsigned char> vchPubKeyFound;
-            if (!keystore.GetPubKey(Hash160(vchPubKey), vchPubKeyFound))
-                return false;
-            if (vchPubKeyFound != vchPubKey)
-                return false;
-        }
-        else if (item.first == OP_PUBKEYHASH)
-        {
-            if (!keystore.HaveKey(uint160(item.second)))
-                return false;
-        }
-        else
+        BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolutions[i])
         {
-            return false;
+            ++keysRequired;
+            if (item.first == OP_PUBKEY)
+            {
+                const valtype& vchPubKey = item.second;
+                vector<unsigned char> vchPubKeyFound;
+                if (keystore.GetPubKey(Hash160(vchPubKey), vchPubKeyFound) && vchPubKeyFound == vchPubKey)
+                    ++keysFound;
+            }
+            else if (item.first == OP_PUBKEYHASH)
+            {
+                if (keystore.HaveKey(uint160(item.second)))
+                    ++keysFound;
+            }
         }
     }
 
-    return true;
+    // Only consider transactions "mine" if we own ALL the
+    // keys involved. multi-signature transactions that are
+    // partially owned (somebody else has a key that can spend
+    // them) enable spend-out-from-under-you attacks, especially
+    // for shared-wallet situations.
+    return (keysFound == keysRequired);
 }
 
 bool ExtractAddress(const CScript& scriptPubKey, const CKeyStore* keystore, CBitcoinAddress& addressRet)
 {
-    vector<pair<opcodetype, valtype> > vSolution;
-    if (!Solver(scriptPubKey, vSolution))
+    vector<vector<pair<opcodetype, valtype> > > vSolutions;
+    if (!Solver(scriptPubKey, vSolutions))
         return false;
 
-    BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
+    for (int i = 0; i < vSolutions.size(); i++)
     {
+        if (vSolutions[i].size() != 1)
+            continue; // Can't return more than one address...
+
+        PAIRTYPE(opcodetype, valtype)& item = vSolutions[i][0];
         if (item.first == OP_PUBKEY)
             addressRet.SetPubKey(item.second);
         else if (item.first == OP_PUBKEYHASH)
@@ -1132,7 +1203,6 @@ bool ExtractAddress(const CScript& scriptPubKey, const CKeyStore* keystore, CBit
         if (keystore == NULL || keystore->HaveKey(addressRet))
             return true;
     }
-
     return false;
 }
 
@@ -1192,3 +1262,22 @@ bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsig
 
     return true;
 }
+
+void CScript::SetMultisigAnd(const std::vector<CKey>& keys)
+{
+    assert(keys.size() >= 2);
+    this->clear();
+    *this << OP_2 << keys[0].GetPubKey() << keys[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+}
+void CScript::SetMultisigOr(const std::vector<CKey>& keys)
+{
+    assert(keys.size() >= 2);
+    this->clear();
+    *this << OP_1 << keys[0].GetPubKey() << keys[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+}
+void CScript::SetMultisigEscrow(const std::vector<CKey>& keys)
+{
+    assert(keys.size() >= 3);
+    this->clear();
+    *this << OP_2 << keys[0].GetPubKey() << keys[1].GetPubKey() << keys[1].GetPubKey() << OP_3 << OP_CHECKMULTISIG;
+}
diff --git a/src/script.h b/src/script.h
index e61ea2fd7e..a5a1e1868c 100644
--- a/src/script.h
+++ b/src/script.h
@@ -574,6 +574,13 @@ public:
         return true;
     }
 
+    static int DecodeOP_N(opcodetype opcode)
+    {
+        if (opcode == OP_0)
+            return 0;
+        assert(opcode >= OP_1 && opcode <= OP_16);
+        return (int)opcode - (int)(OP_1 - 1);
+    }
 
     void FindAndDelete(const CScript& b)
     {
@@ -625,21 +632,6 @@ public:
     }
 
 
-    CBitcoinAddress GetBitcoinAddress() const
-    {
-        opcodetype opcode;
-        std::vector<unsigned char> vch;
-        CScript::const_iterator pc = begin();
-        if (!GetOp(pc, opcode, vch) || opcode != OP_DUP) return 0;
-        if (!GetOp(pc, opcode, vch) || opcode != OP_HASH160) return 0;
-        if (!GetOp(pc, opcode, vch) || vch.size() != sizeof(uint160)) return 0;
-        uint160 hash160 = uint160(vch);
-        if (!GetOp(pc, opcode, vch) || opcode != OP_EQUALVERIFY) return 0;
-        if (!GetOp(pc, opcode, vch) || opcode != OP_CHECKSIG) return 0;
-        if (pc != end()) return 0;
-        return CBitcoinAddress(hash160);
-    }
-
     void SetBitcoinAddress(const CBitcoinAddress& address)
     {
         this->clear();
@@ -650,6 +642,9 @@ public:
     {
         SetBitcoinAddress(CBitcoinAddress(vchPubKey));
     }
+    void SetMultisigAnd(const std::vector<CKey>& keys);
+    void SetMultisigOr(const std::vector<CKey>& keys);
+    void SetMultisigEscrow(const std::vector<CKey>& keys);
 
 
     void PrintHex() const
diff --git a/src/test/multisig_tests.cpp b/src/test/multisig_tests.cpp
new file mode 100644
index 0000000000..459d112369
--- /dev/null
+++ b/src/test/multisig_tests.cpp
@@ -0,0 +1,288 @@
+#include <boost/assert.hpp>
+#include <boost/assign/list_of.hpp>
+#include <boost/assign/list_inserter.hpp>
+#include <boost/assign/std/vector.hpp>
+#include <boost/test/unit_test.hpp>
+#include <boost/foreach.hpp>
+#include <boost/tuple/tuple.hpp>
+
+#include <openssl/ec.h>
+#include <openssl/err.h>
+
+#include "keystore.h"
+#include "main.h"
+#include "script.h"
+#include "wallet.h"
+
+using namespace std;
+using namespace boost::assign;
+
+typedef vector<unsigned char> valtype;
+
+extern uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType);
+extern bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType);
+extern bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType);
+extern bool Solver(const CScript& scriptPubKey, vector<vector<pair<opcodetype, valtype> > >& vSolutionsRet);
+
+BOOST_AUTO_TEST_SUITE(multisig_tests)
+
+CScript
+sign_multisig(CScript scriptPubKey, vector<CKey> keys, CTransaction transaction, int whichIn)
+{
+    uint256 hash = SignatureHash(scriptPubKey, transaction, whichIn, SIGHASH_ALL);
+
+    CScript result;
+    result << OP_0; // CHECKMULTISIG bug workaround
+    BOOST_FOREACH(CKey key, keys)
+    {
+        vector<unsigned char> vchSig;
+        BOOST_CHECK(key.Sign(hash, vchSig));
+        vchSig.push_back((unsigned char)SIGHASH_ALL);
+        result << vchSig;
+    }
+    return result;
+}
+
+BOOST_AUTO_TEST_CASE(multisig_verify)
+{
+    CKey key[4];
+    for (int i = 0; i < 4; i++)
+        key[i].MakeNewKey();
+
+    CScript a_and_b;
+    a_and_b << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+
+    CScript a_or_b;
+    a_or_b << OP_1 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+
+    CScript escrow;
+    escrow << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << key[2].GetPubKey() << OP_3 << OP_CHECKMULTISIG;
+
+    CTransaction txFrom;  // Funding transaction
+    txFrom.vout.resize(3);
+    txFrom.vout[0].scriptPubKey = a_and_b;
+    txFrom.vout[1].scriptPubKey = a_or_b;
+    txFrom.vout[2].scriptPubKey = escrow;
+
+    CTransaction txTo[3]; // Spending transaction
+    for (int i = 0; i < 3; i++)
+    {
+        txTo[i].vin.resize(1);
+        txTo[i].vout.resize(1);
+        txTo[i].vin[0].prevout.n = i;
+        txTo[i].vin[0].prevout.hash = txFrom.GetHash();
+        txTo[i].vout[0].nValue = 1;
+    }
+
+    vector<CKey> keys;
+    CScript s;
+
+    // Test a AND b:
+    keys.clear();
+    keys += key[0],key[1]; // magic operator+= from boost.assign
+    s = sign_multisig(a_and_b, keys, txTo[0], 0);
+    BOOST_CHECK(VerifyScript(s, a_and_b, txTo[0], 0, 0));
+
+    for (int i = 0; i < 4; i++)
+    {
+        keys.clear();
+        keys += key[i];
+        s = sign_multisig(a_and_b, keys, txTo[0], 0);
+        BOOST_CHECK_MESSAGE(!VerifyScript(s, a_and_b, txTo[0], 0, 0), strprintf("a&b 1: %d", i));
+
+        keys.clear();
+        keys += key[1],key[i];
+        s = sign_multisig(a_and_b, keys, txTo[0], 0);
+        BOOST_CHECK_MESSAGE(!VerifyScript(s, a_and_b, txTo[0], 0, 0), strprintf("a&b 2: %d", i));
+    }
+
+    // Test a OR b:
+    for (int i = 0; i < 4; i++)
+    {
+        keys.clear();
+        keys += key[i];
+        s = sign_multisig(a_or_b, keys, txTo[1], 0);
+        if (i == 0 || i == 1)
+            BOOST_CHECK_MESSAGE(VerifyScript(s, a_or_b, txTo[1], 0, 0), strprintf("a|b: %d", i));
+        else
+            BOOST_CHECK_MESSAGE(!VerifyScript(s, a_or_b, txTo[1], 0, 0), strprintf("a|b: %d", i));
+    }
+    s.clear();
+    s << OP_0 << OP_0;
+    BOOST_CHECK(!VerifyScript(s, a_or_b, txTo[1], 0, 0));
+    s.clear();
+    s << OP_0 << OP_1;
+    BOOST_CHECK(!VerifyScript(s, a_or_b, txTo[1], 0, 0));
+
+
+    for (int i = 0; i < 4; i++)
+        for (int j = 0; j < 4; j++)
+        {
+            keys.clear();
+            keys += key[i],key[j];
+            s = sign_multisig(escrow, keys, txTo[2], 0);
+            if (i < j && i < 3 && j < 3)
+                BOOST_CHECK_MESSAGE(VerifyScript(s, escrow, txTo[2], 0, 0), strprintf("escrow 1: %d %d", i, j));
+            else
+                BOOST_CHECK_MESSAGE(!VerifyScript(s, escrow, txTo[2], 0, 0), strprintf("escrow 2: %d %d", i, j));
+        }
+}
+
+BOOST_AUTO_TEST_CASE(multisig_IsStandard)
+{
+    CKey key[3];
+    for (int i = 0; i < 3; i++)
+        key[i].MakeNewKey();
+
+    CScript a_and_b;
+    a_and_b << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+    BOOST_CHECK(::IsStandard(a_and_b));
+
+    CScript a_or_b;
+    a_or_b  << OP_1 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+    BOOST_CHECK(::IsStandard(a_or_b));
+
+    CScript escrow;
+    escrow << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << key[2].GetPubKey() << OP_3 << OP_CHECKMULTISIG;
+    BOOST_CHECK(::IsStandard(escrow));
+}
+
+BOOST_AUTO_TEST_CASE(multisig_Solver1)
+{
+    // Tests Solver() that returns lists of keys that are
+    // required to satisfy a ScriptPubKey
+    //
+    // Also tests IsMine() and ExtractAddress()
+    //
+    // Note: ExtractAddress for the multisignature transactions
+    // always returns false for this release, even if you have
+    // one key that would satisfy an (a|b) or 2-of-3 keys needed
+    // to spend an escrow transaction.
+    //
+    CBasicKeyStore keystore, emptykeystore;
+    CKey key[3];
+    CBitcoinAddress keyaddr[3];
+    for (int i = 0; i < 3; i++)
+    {
+        key[i].MakeNewKey();
+        keystore.AddKey(key[i]);
+        keyaddr[i].SetPubKey(key[i].GetPubKey());
+    }
+
+    {
+        vector<vector<pair<opcodetype, valtype> > > solutions;
+        CScript s;
+        s << key[0].GetPubKey() << OP_CHECKSIG;
+        BOOST_CHECK(Solver(s, solutions));
+        BOOST_CHECK(solutions.size() == 1);
+        if (solutions.size() == 1)
+            BOOST_CHECK(solutions[0].size() == 1);
+        CBitcoinAddress addr;
+        BOOST_CHECK(ExtractAddress(s, &keystore, addr));
+        BOOST_CHECK(addr == keyaddr[0]);
+        BOOST_CHECK(IsMine(keystore, s));
+        BOOST_CHECK(!IsMine(emptykeystore, s));
+    }
+    {
+        vector<vector<pair<opcodetype, valtype> > > solutions;
+        CScript s;
+        s << OP_DUP << OP_HASH160 << Hash160(key[0].GetPubKey()) << OP_EQUALVERIFY << OP_CHECKSIG;
+        BOOST_CHECK(Solver(s, solutions));
+        BOOST_CHECK(solutions.size() == 1);
+        if (solutions.size() == 1)
+            BOOST_CHECK(solutions[0].size() == 1);
+        CBitcoinAddress addr;
+        BOOST_CHECK(ExtractAddress(s, &keystore, addr));
+        BOOST_CHECK(addr == keyaddr[0]);
+        BOOST_CHECK(IsMine(keystore, s));
+        BOOST_CHECK(!IsMine(emptykeystore, s));
+    }
+    {
+        vector<vector<pair<opcodetype, valtype> > > solutions;
+        CScript s;
+        s << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+        BOOST_CHECK(Solver(s, solutions));
+        BOOST_CHECK(solutions.size() == 1);
+        if (solutions.size() == 1)
+            BOOST_CHECK(solutions[0].size() == 2);
+        CBitcoinAddress addr;
+        BOOST_CHECK(!ExtractAddress(s, &keystore, addr));
+        BOOST_CHECK(IsMine(keystore, s));
+        BOOST_CHECK(!IsMine(emptykeystore, s));
+    }
+    {
+        vector<vector<pair<opcodetype, valtype> > > solutions;
+        CScript s;
+        s << OP_1 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+        BOOST_CHECK(Solver(s, solutions));
+        BOOST_CHECK(solutions.size() == 2);
+        if (solutions.size() == 2)
+        {
+            BOOST_CHECK(solutions[0].size() == 1);
+            BOOST_CHECK(solutions[1].size() == 1);
+        }
+        CBitcoinAddress addr;
+        BOOST_CHECK(ExtractAddress(s, &keystore, addr));
+        BOOST_CHECK(addr == keyaddr[0]);
+        BOOST_CHECK(IsMine(keystore, s));
+        BOOST_CHECK(!IsMine(emptykeystore, s));
+    }
+    {
+        vector<vector<pair<opcodetype, valtype> > > solutions;
+        CScript s;
+        s << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << key[2].GetPubKey() << OP_3 << OP_CHECKMULTISIG;
+        BOOST_CHECK(Solver(s, solutions));
+        BOOST_CHECK(solutions.size() == 3);
+        if (solutions.size() == 3)
+        {
+            BOOST_CHECK(solutions[0].size() == 2);
+            BOOST_CHECK(solutions[1].size() == 2);
+            BOOST_CHECK(solutions[2].size() == 2);
+        }
+    }
+}
+
+BOOST_AUTO_TEST_CASE(multisig_Sign)
+{
+    // Test SignSignature() (and therefore the version of Solver() that signs transactions)
+    CBasicKeyStore keystore;
+    CKey key[4];
+    for (int i = 0; i < 4; i++)
+    {
+        key[i].MakeNewKey();
+        keystore.AddKey(key[i]);
+    }
+
+    CScript a_and_b;
+    a_and_b << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+
+    CScript a_or_b;
+    a_or_b  << OP_1 << key[0].GetPubKey() << key[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+
+    CScript escrow;
+    escrow << OP_2 << key[0].GetPubKey() << key[1].GetPubKey() << key[2].GetPubKey() << OP_3 << OP_CHECKMULTISIG;
+
+    CTransaction txFrom;  // Funding transaction
+    txFrom.vout.resize(3);
+    txFrom.vout[0].scriptPubKey = a_and_b;
+    txFrom.vout[1].scriptPubKey = a_or_b;
+    txFrom.vout[2].scriptPubKey = escrow;
+
+    CTransaction txTo[3]; // Spending transaction
+    for (int i = 0; i < 3; i++)
+    {
+        txTo[i].vin.resize(1);
+        txTo[i].vout.resize(1);
+        txTo[i].vin[0].prevout.n = i;
+        txTo[i].vin[0].prevout.hash = txFrom.GetHash();
+        txTo[i].vout[0].nValue = 1;
+    }
+
+    for (int i = 0; i < 3; i++)
+    {
+        BOOST_CHECK_MESSAGE(SignSignature(keystore, txFrom, txTo[i], 0), strprintf("SignSignature %d", i));
+    }
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/wallet.cpp b/src/wallet.cpp
index 87f5dfd659..a662111d49 100644
--- a/src/wallet.cpp
+++ b/src/wallet.cpp
@@ -997,12 +997,11 @@ bool CWallet::CreateTransaction(const vector<pair<CScript, int64> >& vecSend, CW
                     vector<unsigned char> vchPubKey = reservekey.GetReservedKey();
                     // assert(mapKeys.count(vchPubKey));
 
-                    // Fill a vout to ourself, using same address type as the payment
+                    // Fill a vout to ourself
+                    // TODO: pass in scriptChange instead of reservekey so
+                    // change transaction isn't always pay-to-bitcoin-address
                     CScript scriptChange;
-                    if (vecSend[0].first.GetBitcoinAddress().IsValid())
-                        scriptChange.SetBitcoinAddress(vchPubKey);
-                    else
-                        scriptChange << vchPubKey << OP_CHECKSIG;
+                    scriptChange.SetBitcoinAddress(vchPubKey);
 
                     // Insert change txn at random position:
                     vector<CTxOut>::iterator position = wtxNew.vout.begin()+GetRandInt(wtxNew.vout.size());