OP_EVAL implementation

OP_EVAL is a new opcode that evaluates an item on the stack as a script.
It enables a new type of bitcoin address that needs an arbitrarily
complex script to redeem.

1 files changed, 488 insertions, 168 deletions

diff --git a/src/script.cpp b/src/script.cpp
index 6a7913b0d5..c103d57510 100644
--- a/src/script.cpp
+++ b/src/script.cpp
@@ -70,20 +70,186 @@ static inline void popstack(vector<valtype>& stack)
 }
 
 
-bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, int nHashType)
+const char* GetTxnTypeName(txntype t)
+{
+    switch (t)
+    {
+    case TX_NONSTANDARD: return "nonstandard";
+    case TX_PUBKEY: return "pubkey";
+    case TX_PUBKEYHASH: return "pubkeyhash";
+    case TX_SCRIPTHASH: return "scripthash";
+    case TX_MULTISIG: return "multisig";
+    }
+    return NULL;
+}
+
+
+const char* GetOpName(opcodetype opcode)
+{
+    switch (opcode)
+    {
+    // push value
+    case OP_0                      : return "0";
+    case OP_PUSHDATA1              : return "OP_PUSHDATA1";
+    case OP_PUSHDATA2              : return "OP_PUSHDATA2";
+    case OP_PUSHDATA4              : return "OP_PUSHDATA4";
+    case OP_1NEGATE                : return "-1";
+    case OP_RESERVED               : return "OP_RESERVED";
+    case OP_1                      : return "1";
+    case OP_2                      : return "2";
+    case OP_3                      : return "3";
+    case OP_4                      : return "4";
+    case OP_5                      : return "5";
+    case OP_6                      : return "6";
+    case OP_7                      : return "7";
+    case OP_8                      : return "8";
+    case OP_9                      : return "9";
+    case OP_10                     : return "10";
+    case OP_11                     : return "11";
+    case OP_12                     : return "12";
+    case OP_13                     : return "13";
+    case OP_14                     : return "14";
+    case OP_15                     : return "15";
+    case OP_16                     : return "16";
+
+    // control
+    case OP_NOP                    : return "OP_NOP";
+    case OP_VER                    : return "OP_VER";
+    case OP_IF                     : return "OP_IF";
+    case OP_NOTIF                  : return "OP_NOTIF";
+    case OP_VERIF                  : return "OP_VERIF";
+    case OP_VERNOTIF               : return "OP_VERNOTIF";
+    case OP_ELSE                   : return "OP_ELSE";
+    case OP_ENDIF                  : return "OP_ENDIF";
+    case OP_VERIFY                 : return "OP_VERIFY";
+    case OP_RETURN                 : return "OP_RETURN";
+
+    // stack ops
+    case OP_TOALTSTACK             : return "OP_TOALTSTACK";
+    case OP_FROMALTSTACK           : return "OP_FROMALTSTACK";
+    case OP_2DROP                  : return "OP_2DROP";
+    case OP_2DUP                   : return "OP_2DUP";
+    case OP_3DUP                   : return "OP_3DUP";
+    case OP_2OVER                  : return "OP_2OVER";
+    case OP_2ROT                   : return "OP_2ROT";
+    case OP_2SWAP                  : return "OP_2SWAP";
+    case OP_IFDUP                  : return "OP_IFDUP";
+    case OP_DEPTH                  : return "OP_DEPTH";
+    case OP_DROP                   : return "OP_DROP";
+    case OP_DUP                    : return "OP_DUP";
+    case OP_NIP                    : return "OP_NIP";
+    case OP_OVER                   : return "OP_OVER";
+    case OP_PICK                   : return "OP_PICK";
+    case OP_ROLL                   : return "OP_ROLL";
+    case OP_ROT                    : return "OP_ROT";
+    case OP_SWAP                   : return "OP_SWAP";
+    case OP_TUCK                   : return "OP_TUCK";
+
+    // splice ops
+    case OP_CAT                    : return "OP_CAT";
+    case OP_SUBSTR                 : return "OP_SUBSTR";
+    case OP_LEFT                   : return "OP_LEFT";
+    case OP_RIGHT                  : return "OP_RIGHT";
+    case OP_SIZE                   : return "OP_SIZE";
+
+    // bit logic
+    case OP_INVERT                 : return "OP_INVERT";
+    case OP_AND                    : return "OP_AND";
+    case OP_OR                     : return "OP_OR";
+    case OP_XOR                    : return "OP_XOR";
+    case OP_EQUAL                  : return "OP_EQUAL";
+    case OP_EQUALVERIFY            : return "OP_EQUALVERIFY";
+    case OP_RESERVED1              : return "OP_RESERVED1";
+    case OP_RESERVED2              : return "OP_RESERVED2";
+
+    // numeric
+    case OP_1ADD                   : return "OP_1ADD";
+    case OP_1SUB                   : return "OP_1SUB";
+    case OP_2MUL                   : return "OP_2MUL";
+    case OP_2DIV                   : return "OP_2DIV";
+    case OP_NEGATE                 : return "OP_NEGATE";
+    case OP_ABS                    : return "OP_ABS";
+    case OP_NOT                    : return "OP_NOT";
+    case OP_0NOTEQUAL              : return "OP_0NOTEQUAL";
+    case OP_ADD                    : return "OP_ADD";
+    case OP_SUB                    : return "OP_SUB";
+    case OP_MUL                    : return "OP_MUL";
+    case OP_DIV                    : return "OP_DIV";
+    case OP_MOD                    : return "OP_MOD";
+    case OP_LSHIFT                 : return "OP_LSHIFT";
+    case OP_RSHIFT                 : return "OP_RSHIFT";
+    case OP_BOOLAND                : return "OP_BOOLAND";
+    case OP_BOOLOR                 : return "OP_BOOLOR";
+    case OP_NUMEQUAL               : return "OP_NUMEQUAL";
+    case OP_NUMEQUALVERIFY         : return "OP_NUMEQUALVERIFY";
+    case OP_NUMNOTEQUAL            : return "OP_NUMNOTEQUAL";
+    case OP_LESSTHAN               : return "OP_LESSTHAN";
+    case OP_GREATERTHAN            : return "OP_GREATERTHAN";
+    case OP_LESSTHANOREQUAL        : return "OP_LESSTHANOREQUAL";
+    case OP_GREATERTHANOREQUAL     : return "OP_GREATERTHANOREQUAL";
+    case OP_MIN                    : return "OP_MIN";
+    case OP_MAX                    : return "OP_MAX";
+    case OP_WITHIN                 : return "OP_WITHIN";
+
+    // crypto
+    case OP_RIPEMD160              : return "OP_RIPEMD160";
+    case OP_SHA1                   : return "OP_SHA1";
+    case OP_SHA256                 : return "OP_SHA256";
+    case OP_HASH160                : return "OP_HASH160";
+    case OP_HASH256                : return "OP_HASH256";
+    case OP_CODESEPARATOR          : return "OP_CODESEPARATOR";
+    case OP_CHECKSIG               : return "OP_CHECKSIG";
+    case OP_CHECKSIGVERIFY         : return "OP_CHECKSIGVERIFY";
+    case OP_CHECKMULTISIG          : return "OP_CHECKMULTISIG";
+    case OP_CHECKMULTISIGVERIFY    : return "OP_CHECKMULTISIGVERIFY";
+
+    // meta
+    case OP_EVAL                   : return "OP_EVAL";
+
+    // expanson
+    case OP_NOP2                   : return "OP_NOP2";
+    case OP_NOP3                   : return "OP_NOP3";
+    case OP_NOP4                   : return "OP_NOP4";
+    case OP_NOP5                   : return "OP_NOP5";
+    case OP_NOP6                   : return "OP_NOP6";
+    case OP_NOP7                   : return "OP_NOP7";
+    case OP_NOP8                   : return "OP_NOP8";
+    case OP_NOP9                   : return "OP_NOP9";
+    case OP_NOP10                  : return "OP_NOP10";
+
+
+
+    // template matching params
+    case OP_SCRIPTHASH             : return "OP_SCRIPTHASH";
+    case OP_PUBKEYHASH             : return "OP_PUBKEYHASH";
+    case OP_PUBKEY                 : return "OP_PUBKEY";
+
+    case OP_INVALIDOPCODE          : return "OP_INVALIDOPCODE";
+    default:
+        return "OP_UNKNOWN";
+    }
+}
+
+
+//
+// Returns true if script is valid.
+//
+bool EvalScriptInner(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, int nHashType,
+                     CScript::const_iterator pbegincodehash, CScript::const_iterator pendcodehash, int& nOpCount, int& nSigOpCount, int nRecurseDepth)
 {
     CAutoBN_CTX pctx;
     CScript::const_iterator pc = script.begin();
     CScript::const_iterator pend = script.end();
-    CScript::const_iterator pbegincodehash = script.begin();
     opcodetype opcode;
     valtype vchPushValue;
     vector<bool> vfExec;
     vector<valtype> altstack;
     if (script.size() > 10000)
         return false;
-    int nOpCount = 0;
 
+    // Limit OP_EVAL recursion
+    if (nRecurseDepth > 2)
+        return false;
 
     try
     {
@@ -155,7 +321,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, co
                 // Control
                 //
                 case OP_NOP:
-                case OP_NOP1: case OP_NOP2: case OP_NOP3: case OP_NOP4: case OP_NOP5:
+                case OP_NOP2: case OP_NOP3: case OP_NOP4: case OP_NOP5:
                 case OP_NOP6: case OP_NOP7: case OP_NOP8: case OP_NOP9: case OP_NOP10:
                 break;
 
@@ -751,12 +917,13 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, co
                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");
 
                     // Subset of script starting at the most recent codeseparator
-                    CScript scriptCode(pbegincodehash, pend);
+                    CScript scriptCode(pbegincodehash, pendcodehash);
 
                     // Drop the signature, since there's no way for a signature to sign itself
                     scriptCode.FindAndDelete(CScript(vchSig));
 
                     bool fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType);
+                    nSigOpCount++;
 
                     popstack(stack);
                     popstack(stack);
@@ -800,7 +967,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, co
                         return false;
 
                     // Subset of script starting at the most recent codeseparator
-                    CScript scriptCode(pbegincodehash, pend);
+                    CScript scriptCode(pbegincodehash, pendcodehash);
 
                     // Drop the signatures, since there's no way for a signature to sign itself
                     for (int k = 0; k < nSigsCount; k++)
@@ -823,6 +990,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, co
                         }
                         ikey++;
                         nKeysCount--;
+                        nSigOpCount++;
 
                         // If there are more signatures left than keys left,
                         // then too many signatures have failed
@@ -844,6 +1012,26 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, co
                 }
                 break;
 
+                case OP_EVAL:
+                {
+                    // Evaluate the top item on the stack as a Script
+                    // [serialized script ] -- [result(s) of executing script]
+                    if (stack.size() < 1)
+                        return false;
+                    valtype& vchScript = stacktop(-1);
+                    CScript subscript(vchScript.begin(), vchScript.end());
+                    popstack(stack);
+                    
+                    // Codeseparators not allowed
+                    if (subscript.Find(OP_CODESEPARATOR))
+                        return false;
+
+                    if (!EvalScriptInner(stack, subscript, txTo, nIn, nHashType,
+                                         pbegincodehash, pendcodehash, nOpCount, nSigOpCount, nRecurseDepth++))
+                        return false;
+                }
+                break;
+
                 default:
                     return false;
             }
@@ -865,6 +1053,17 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, co
     return true;
 }
 
+bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script,
+                const CTransaction& txTo, unsigned int nIn, int nHashType, int& nSigOpCountRet)
+{
+    CScript::const_iterator pbegincodehash = script.begin();
+    CScript::const_iterator pendcodehash = script.end();
+
+    int nOpCount = 0;
+    return EvalScriptInner(stack, script, txTo, nIn, nHashType, pbegincodehash, pendcodehash,
+                           nOpCount, nSigOpCountRet, 0);
+}
+
 
 
 
@@ -964,38 +1163,35 @@ bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CSc
 
 
 //
-// Returns lists of public keys (or public key hashes), any one of which can
-// satisfy scriptPubKey
+// Return public keys or hashes from scriptPubKey, for 'standard' transaction types.
 //
-bool Solver(const CScript& scriptPubKey, vector<vector<pair<opcodetype, valtype> > >& vSolutionsRet)
+bool Solver(const CScript& scriptPubKey, txntype& typeRet, vector<vector<unsigned char> >& vSolutionsRet)
 {
     // Templates
-    static vector<CScript> vTemplates;
-    if (vTemplates.empty())
+    static map<txntype, CScript> mTemplates;
+    if (mTemplates.empty())
     {
         // Standard tx, sender provides pubkey, receiver adds signature
-        vTemplates.push_back(CScript() << OP_PUBKEY << OP_CHECKSIG);
+        mTemplates.insert(make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG));
 
         // 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);
+        mTemplates.insert(make_pair(TX_PUBKEYHASH, CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG));
 
-        // 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 N pubkeys, receivers provides M signatures
+        mTemplates.insert(make_pair(TX_MULTISIG, CScript() << OP_SMALLINTEGER << OP_PUBKEYS << OP_SMALLINTEGER << 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);
+        // Sender provides script hash, receiver provides script and
+        // as many signatures as required to satisfy script
+        mTemplates.insert(make_pair(TX_SCRIPTHASH, CScript() << OP_DUP << OP_HASH160 << OP_SCRIPTHASH << OP_EQUALVERIFY << OP_EVAL));
     }
 
     // Scan templates
     const CScript& script1 = scriptPubKey;
-    BOOST_FOREACH(const CScript& script2, vTemplates)
+    BOOST_FOREACH(const PAIRTYPE(txntype, CScript)& tplate, mTemplates)
     {
+        const CScript& script2 = tplate.second;
         vSolutionsRet.clear();
 
-        vector<pair<opcodetype, valtype> > currentSolution;
         opcodetype opcode1, opcode2;
         vector<unsigned char> vch1, vch2;
 
@@ -1006,218 +1202,333 @@ bool Solver(const CScript& scriptPubKey, vector<vector<pair<opcodetype, valtype>
         {
             if (pc1 == script1.end() && pc2 == script2.end())
             {
-                return !vSolutionsRet.empty();
+                // Found a match
+                typeRet = tplate.first;
+                if (typeRet == TX_MULTISIG)
+                {
+                    // Additional checks for TX_MULTISIG:
+                    unsigned char m = vSolutionsRet.front()[0];
+                    unsigned char n = vSolutionsRet.back()[0];
+                    if (m < 1 || n < 1 || m > n || vSolutionsRet.size()-2 != n)
+                        return false;
+                }
+                return true;
             }
             if (!script1.GetOp(pc1, opcode1, vch1))
                 break;
             if (!script2.GetOp(pc2, opcode2, vch2))
                 break;
+
+            // Template matching opcodes:
+            if (opcode2 == OP_PUBKEYS)
+            {
+                while (vch1.size() >= 33 && vch1.size() <= 120)
+                {
+                    vSolutionsRet.push_back(vch1);
+                    if (!script1.GetOp(pc1, opcode1, vch1))
+                        break;
+                }
+                if (!script2.GetOp(pc2, opcode2, vch2))
+                    break;
+                // Normal situation is to fall through
+                // to other if/else statments
+            }
+
             if (opcode2 == OP_PUBKEY)
             {
                 if (vch1.size() < 33 || vch1.size() > 120)
                     break;
-                currentSolution.push_back(make_pair(opcode2, vch1));
+                vSolutionsRet.push_back(vch1);
             }
             else if (opcode2 == OP_PUBKEYHASH)
             {
                 if (vch1.size() != sizeof(uint160))
                     break;
-                currentSolution.push_back(make_pair(opcode2, vch1));
+                vSolutionsRet.push_back(vch1);
             }
-            else if (opcode2 == OP_CHECKSIG)
+            else if (opcode2 == OP_SCRIPTHASH)
             {
-                vSolutionsRet.push_back(currentSolution);
-                currentSolution.clear();
+                if (vch1.size() != sizeof(uint160))
+                    break;
+                vSolutionsRet.push_back(vch1);
             }
-            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)
+            else if (opcode2 == OP_SMALLINTEGER)
+            {   // Single-byte small integer pushed onto vSolutions
+                if (opcode1 == OP_0 ||
+                    (opcode1 >= OP_1 && opcode1 <= OP_16))
                 {
-                    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();
+                    char n = (char)CScript::DecodeOP_N(opcode1);
+                    vSolutionsRet.push_back(valtype(1, n));
                 }
+                else
+                    break;
             }
             else if (opcode1 != opcode2 || vch1 != vch2)
             {
+                // Others must match exactly
                 break;
             }
         }
     }
 
     vSolutionsRet.clear();
+    typeRet = TX_NONSTANDARD;
     return false;
 }
 
 
-bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)
+bool Sign1(const CBitcoinAddress& address, const CKeyStore& keystore, uint256 hash, int nHashType, CScript& scriptSigRet)
 {
-    scriptSigRet.clear();
+    CKey key;
+    if (!keystore.GetKey(address, key))
+        return false;
 
-    vector<vector<pair<opcodetype, valtype> > > vSolutions;
-    if (!Solver(scriptPubKey, vSolutions))
+    vector<unsigned char> vchSig;
+    if (!key.Sign(hash, vchSig))
         return false;
+    vchSig.push_back((unsigned char)nHashType);
+    scriptSigRet << vchSig;
 
-    // See if we have all the keys for any of the solutions:
-    int whichSolution = -1;
-    for (int i = 0; i < vSolutions.size(); i++)
-    {
-        int keysFound = 0;
-        CScript scriptSig;
+    return true;
+}
 
-        BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolutions[i])
-        {
-            if (item.first == OP_PUBKEY)
-            {
-                const valtype& vchPubKey = item.second;
-                CKey key;
-                vector<unsigned char> 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)
-            {
-                CKey key;
-                vector<unsigned char> vchSig;
-                if (keystore.GetKey(uint160(item.second), key) 
-                    && hash != 0 && key.Sign(hash, vchSig))
-                {
-                    vchSig.push_back((unsigned char)nHashType);
-                    scriptSig << vchSig << key.GetPubKey();
-                    ++keysFound;
-                }
-            }
-        }
-        if (keysFound == vSolutions[i].size())
+bool SignN(const vector<valtype>& multisigdata, const CKeyStore& keystore, uint256 hash, int nHashType, CScript& scriptSigRet)
+{
+    int nSigned = 0;
+    int nRequired = multisigdata.front()[0];
+    for (vector<valtype>::const_iterator it = multisigdata.begin()+1; it != multisigdata.begin()+multisigdata.size()-1; it++)
+    {
+        const valtype& pubkey = *it;
+        CBitcoinAddress address;
+        address.SetPubKey(pubkey);
+        if (Sign1(address, keystore, hash, nHashType, scriptSigRet))
         {
-            whichSolution = i;
-            scriptSigRet = scriptSig;
-            break;
+            ++nSigned;
+            if (nSigned == nRequired) break;
         }
     }
-    if (whichSolution == -1)
+    return nSigned==nRequired;
+}
+
+//
+// Sign scriptPubKey with private keys stored in keystore, given transaction hash and hash type.
+// Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed).
+// Returns true if scriptPubKey could be completely satisified.
+//
+bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)
+{
+    scriptSigRet.clear();
+
+    txntype whichType;
+    vector<valtype> vSolutions;
+    if (!Solver(scriptPubKey, whichType, vSolutions))
         return false;
 
-    // CHECKMULTISIG bug workaround:
-    if (vSolutions.size() != 1 ||
-        vSolutions[0].size() != 1)
+    CBitcoinAddress address;
+    valtype subscript;
+    switch (whichType)
     {
-        scriptSigRet.insert(scriptSigRet.begin(), OP_0);
+    case TX_NONSTANDARD:
+        return false;
+    case TX_PUBKEY:
+        address.SetPubKey(vSolutions[0]);
+        return Sign1(address, keystore, hash, nHashType, scriptSigRet);
+    case TX_PUBKEYHASH:
+        address.SetHash160(uint160(vSolutions[0]));
+        if (!Sign1(address, keystore, hash, nHashType, scriptSigRet))
+            return false;
+        else
+        {
+            valtype vch;
+            keystore.GetPubKey(address, vch);
+            scriptSigRet << vch;
+        }
+        break;
+    case TX_SCRIPTHASH:
+        if (!keystore.GetCScript(uint160(vSolutions[0]), subscript))
+            return false;
+        if (!Solver(keystore, CScript(subscript.begin(), subscript.end()), hash, nHashType, scriptSigRet))
+            return false;
+        if (hash != 0)
+            scriptSigRet << subscript; // signatures AND serialized script
+        break;
+    case TX_MULTISIG:
+        scriptSigRet << OP_0; // workaround CHECKMULTISIG bug
+        return (SignN(vSolutions, keystore, hash, nHashType, scriptSigRet));
     }
-
     return true;
 }
 
 
 bool IsStandard(const CScript& scriptPubKey)
 {
-    vector<vector<pair<opcodetype, valtype> > > vSolutions;
-    return Solver(scriptPubKey, vSolutions);
+    vector<valtype> vSolutions;
+    txntype whichType;
+    if (!Solver(scriptPubKey, whichType, vSolutions))
+        return false;
+
+    if (whichType == TX_MULTISIG)
+    {
+        unsigned char m = vSolutions.front()[0];
+        unsigned char n = vSolutions.back()[0];
+        // Support up to x-of-3 multisig txns as standard
+        if (n < 1 || n > 3)
+            return false;
+        if (m < 1 || m > n)
+            return false;
+    }
+
+    return whichType != TX_NONSTANDARD;
 }
 
 
+int HaveKeys(const vector<valtype>& pubkeys, const CKeyStore& keystore)
+{
+    int nResult = 0;
+    BOOST_FOREACH(const valtype& pubkey, pubkeys)
+    {
+        CBitcoinAddress address;
+        address.SetPubKey(pubkey);
+        if (keystore.HaveKey(address))
+            ++nResult;
+    }
+    return nResult;
+}
+
 bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey)
 {
-    vector<vector<pair<opcodetype, valtype> > > vSolutions;
-    if (!Solver(scriptPubKey, vSolutions))
+    vector<valtype> vSolutions;
+    txntype whichType;
+    if (!Solver(scriptPubKey, whichType, vSolutions))
         return false;
 
-    int keysFound = 0;
-    int keysRequired = 0;
-    for (int i = 0; i < vSolutions.size(); i++)
+    CBitcoinAddress address;
+    switch (whichType)
     {
-        BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolutions[i])
-        {
-            ++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;
-            }
-        }
+    case TX_NONSTANDARD:
+        return false;
+    case TX_PUBKEY:
+        address.SetPubKey(vSolutions[0]);
+        return keystore.HaveKey(address);
+    case TX_PUBKEYHASH:
+        address.SetHash160(uint160(vSolutions[0]));
+        return keystore.HaveKey(address);
+    case TX_SCRIPTHASH:
+    {
+        valtype subscript;
+        if (!keystore.GetCScript(uint160(vSolutions[0]), subscript))
+            return false;
+        return IsMine(keystore, CScript(subscript.begin(), subscript.end()));
     }
-
-    // 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);
+    case TX_MULTISIG:
+    {
+        // 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
+        // in shared-wallet situations.
+        vector<valtype> keys(vSolutions.begin()+1, vSolutions.begin()+vSolutions.size()-1);
+        return HaveKeys(vSolutions, keystore);
+    }
+    }
+    return false;
 }
 
 bool ExtractAddress(const CScript& scriptPubKey, const CKeyStore* keystore, CBitcoinAddress& addressRet)
 {
-    vector<vector<pair<opcodetype, valtype> > > vSolutions;
-    if (!Solver(scriptPubKey, vSolutions))
+    vector<valtype> vSolutions;
+    txntype whichType;
+    if (!Solver(scriptPubKey, whichType, vSolutions))
         return false;
 
-    for (int i = 0; i < vSolutions.size(); i++)
+    if (whichType == TX_PUBKEY)
     {
-        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)
-            addressRet.SetHash160((uint160)item.second);
-        if (keystore == NULL || keystore->HaveKey(addressRet))
-            return true;
+        addressRet.SetPubKey(vSolutions[0]);
+        return true;
     }
+    else if (whichType == TX_PUBKEYHASH)
+    {
+        addressRet.SetHash160(uint160(vSolutions[0]));
+        return true;
+    }
+    else if (whichType == TX_SCRIPTHASH)
+    {
+        addressRet.SetScriptHash160(uint160(vSolutions[0]));
+        return true;
+    }
+    // Multisig txns have more than one address...
     return false;
 }
 
+bool ExtractAddresses(const CScript& scriptPubKey, const CKeyStore* keystore, txntype& typeRet, vector<CBitcoinAddress>& addressRet, int& nRequiredRet)
+{
+    addressRet.clear();
+    typeRet = TX_NONSTANDARD;
+    vector<valtype> vSolutions;
+    if (!Solver(scriptPubKey, typeRet, vSolutions))
+        return false;
 
+    if (typeRet == TX_MULTISIG)
+    {
+        nRequiredRet = vSolutions.front()[0];
+        int n = vSolutions.back()[0];
+        for (vector<valtype>::const_iterator it = vSolutions.begin()+1; it != vSolutions.begin()+vSolutions.size()-1; it++)
+        {
+            CBitcoinAddress address;
+            address.SetPubKey(*it);
+            addressRet.push_back(address);
+        }
+    }
+    else
+    {
+        nRequiredRet = 1;
+        CBitcoinAddress address;
+        if (typeRet == TX_PUBKEYHASH)
+            address.SetHash160(uint160(vSolutions.front()));
+        else if (typeRet == TX_SCRIPTHASH)
+            address.SetScriptHash160(uint160(vSolutions.front()));
+        else if (typeRet == TX_PUBKEY)
+            address.SetPubKey(vSolutions.front());
+        addressRet.push_back(address);
+    }
 
-bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType)
+    return true;
+}
+
+bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int& nSigOpCountRet, int nHashType)
 {
     vector<vector<unsigned char> > stack;
-    if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))
+    if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType, nSigOpCountRet))
         return false;
-    if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))
+    if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType, nSigOpCountRet))
         return false;
     if (stack.empty())
         return false;
-    return CastToBool(stack.back());
+    bool fResult = CastToBool(stack.back());
+
+    // This code should be removed when a compatibility-breaking block chain split has passed.
+    // Special check for OP_EVAL backwards-compatibility: if scriptPubKey or scriptSig contains
+    // OP_EVAL, then result must be identical if OP_EVAL is treated as a no-op:
+    if (scriptSig.Find(OP_EVAL)+scriptPubKey.Find(OP_EVAL) > 0)
+    {
+        int nUnused = 0;
+        stack.clear();
+        CScript sigCopy = scriptSig;
+        sigCopy.FindAndDelete(CScript(OP_EVAL));
+        CScript pubKeyCopy = scriptPubKey;
+        pubKeyCopy.FindAndDelete(CScript(OP_EVAL));
+
+        if (!EvalScript(stack, sigCopy, txTo, nIn, nHashType, nUnused))
+            return false;
+        if (!EvalScript(stack, pubKeyCopy, txTo, nIn, nHashType, nUnused))
+            return false;
+        if (stack.empty())
+            return false;
+        if (fResult != CastToBool(stack.back()))
+            return false;
+    }
+
+    return fResult;
 }
 
 
@@ -1238,15 +1549,16 @@ bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTrans
     txin.scriptSig = scriptPrereq + txin.scriptSig;
 
     // Test solution
+    int nUnused = 0;
     if (scriptPrereq.empty())
-        if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, 0))
+        if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nUnused, 0))
             return false;
 
     return true;
 }
 
 
-bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType)
+bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int& nSigOpCountRet, int nHashType)
 {
     assert(nIn < txTo.vin.size());
     const CTxIn& txin = txTo.vin[nIn];
@@ -1257,27 +1569,35 @@ bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsig
     if (txin.prevout.hash != txFrom.GetHash())
         return false;
 
-    if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nHashType))
+    if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nSigOpCountRet, nHashType))
         return false;
 
     return true;
 }
 
-void CScript::SetMultisigAnd(const std::vector<CKey>& keys)
+void CScript::SetBitcoinAddress(const CBitcoinAddress& address)
 {
-    assert(keys.size() >= 2);
     this->clear();
-    *this << OP_2 << keys[0].GetPubKey() << keys[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+    if (address.IsScript())
+        *this << OP_DUP << OP_HASH160 << address.GetHash160() << OP_EQUALVERIFY << OP_EVAL;
+    else
+        *this << OP_DUP << OP_HASH160 << address.GetHash160() << OP_EQUALVERIFY << OP_CHECKSIG;
 }
-void CScript::SetMultisigOr(const std::vector<CKey>& keys)
+
+void CScript::SetMultisig(int nRequired, const std::vector<CKey>& keys)
 {
-    assert(keys.size() >= 2);
     this->clear();
-    *this << OP_1 << keys[0].GetPubKey() << keys[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
+
+    *this << EncodeOP_N(nRequired);
+    BOOST_FOREACH(const CKey& key, keys)
+        *this << key.GetPubKey();
+    *this << EncodeOP_N(keys.size()) << OP_CHECKMULTISIG;
 }
-void CScript::SetMultisigEscrow(const std::vector<CKey>& keys)
+
+void CScript::SetEval(const CScript& subscript)
 {
-    assert(keys.size() >= 3);
+    assert(!subscript.empty());
+    uint160 subscriptHash = Hash160(subscript);
     this->clear();
-    *this << OP_2 << keys[0].GetPubKey() << keys[1].GetPubKey() << keys[1].GetPubKey() << OP_3 << OP_CHECKMULTISIG;
+    *this << OP_DUP << OP_HASH160 << subscriptHash << OP_EQUALVERIFY << OP_EVAL;
 }