Relax IsStandard rules for pay-to-script-hash transactions

Relax the AreInputsStandard() tests for P2SH transactions --
allow any Script in a P2SH transaction to be relayed/mined,
as long as it has 15 or fewer signature operations.

Rationale: https://gist.github.com/gavinandresen/88be40c141bc67acb247

I don't have an easy way to test this, but the code changes are
straightforward and I've updated the AreInputsStandard unit tests.

3 files changed, 97 insertions, 66 deletions

diff --git a/src/main.cpp b/src/main.cpp
index d3f04b95fa..ecabd9ec2c 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -582,15 +582,13 @@ bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime)
 }
 
 //
-// Check transaction inputs, and make sure any
-// pay-to-script-hash transactions are evaluating IsStandard scripts
+// Check transaction inputs to mitigate two
+// potential denial-of-service attacks:
 //
-// Why bother? To avoid denial-of-service attacks; an attacker
-// can submit a standard HASH... OP_EQUAL transaction,
-// which will get accepted into blocks. The redemption
-// script can be anything; an attacker could use a very
-// expensive-to-check-upon-redemption script like:
-//   DUP CHECKSIG DROP ... repeated 100 times... OP_1
+// 1. scriptSigs with extra data stuffed into them,
+//    not consumed by scriptPubKey (or P2SH script)
+// 2. P2SH scripts with a crazy number of expensive
+//    CHECKSIG/CHECKMULTISIG operations
 //
 bool AreInputsStandard(const CTransaction& tx, CCoinsViewCache& mapInputs)
 {
@@ -614,8 +612,9 @@ bool AreInputsStandard(const CTransaction& tx, CCoinsViewCache& mapInputs)
         // Transactions with extra stuff in their scriptSigs are
         // non-standard. Note that this EvalScript() call will
         // be quick, because if there are any operations
-        // beside "push data" in the scriptSig the
-        // IsStandard() call returns false
+        // beside "push data" in the scriptSig
+        // IsStandard() will have already returned false
+        // and this method isn't called.
         vector<vector<unsigned char> > stack;
         if (!EvalScript(stack, tx.vin[i].scriptSig, tx, i, false, 0))
             return false;
@@ -627,16 +626,20 @@ bool AreInputsStandard(const CTransaction& tx, CCoinsViewCache& mapInputs)
             CScript subscript(stack.back().begin(), stack.back().end());
             vector<vector<unsigned char> > vSolutions2;
             txnouttype whichType2;
-            if (!Solver(subscript, whichType2, vSolutions2))
-                return false;
-            if (whichType2 == TX_SCRIPTHASH)
-                return false;
-
-            int tmpExpected;
-            tmpExpected = ScriptSigArgsExpected(whichType2, vSolutions2);
-            if (tmpExpected < 0)
-                return false;
-            nArgsExpected += tmpExpected;
+            if (Solver(subscript, whichType2, vSolutions2))
+            {
+                int tmpExpected = ScriptSigArgsExpected(whichType2, vSolutions2);
+                if (tmpExpected < 0)
+                    return false;
+                nArgsExpected += tmpExpected;
+            }
+            else
+            {
+                // Any other Script with less than 15 sigops OK:
+                unsigned int sigops = subscript.GetSigOpCount(true);
+                // ... extra data left on the stack after execution is OK, too:
+                return (sigops <= MAX_P2SH_SIGOPS);
+            }
         }
 
         if (stack.size() != (unsigned int)nArgsExpected)
diff --git a/src/main.h b/src/main.h
index 27041a0026..ff1f742d1e 100644
--- a/src/main.h
+++ b/src/main.h
@@ -43,6 +43,8 @@ static const unsigned int DEFAULT_BLOCK_PRIORITY_SIZE = 50000;
 static const unsigned int MAX_STANDARD_TX_SIZE = 100000;
 /** The maximum allowed number of signature check operations in a block (network rule) */
 static const unsigned int MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE/50;
+/** Maxiumum number of signature check operations in an IsStandard() P2SH script */
+static const unsigned int MAX_P2SH_SIGOPS = 15;
 /** The maximum number of orphan transactions kept in memory */
 static const unsigned int MAX_ORPHAN_TRANSACTIONS = MAX_BLOCK_SIZE/100;
 /** Default for -maxorphanblocks, maximum number of orphan blocks kept in memory */
diff --git a/src/test/script_P2SH_tests.cpp b/src/test/script_P2SH_tests.cpp
index a75593a8b2..6ae2b9cf64 100644
--- a/src/test/script_P2SH_tests.cpp
+++ b/src/test/script_P2SH_tests.cpp
@@ -256,46 +256,61 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     CCoinsView coinsDummy;
     CCoinsViewCache coins(coinsDummy);
     CBasicKeyStore keystore;
-    CKey key[3];
+    CKey key[6];
     vector<CPubKey> keys;
-    for (int i = 0; i < 3; i++)
+    for (int i = 0; i < 6; i++)
     {
         key[i].MakeNewKey(true);
         keystore.AddKey(key[i]);
-        keys.push_back(key[i].GetPubKey());
     }
+    for (int i = 0; i < 3; i++)
+        keys.push_back(key[i].GetPubKey());
 
     CMutableTransaction txFrom;
-    txFrom.vout.resize(6);
+    txFrom.vout.resize(7);
 
     // First three are standard:
     CScript pay1; pay1.SetDestination(key[0].GetPubKey().GetID());
     keystore.AddCScript(pay1);
-    CScript payScriptHash1; payScriptHash1.SetDestination(pay1.GetID());
     CScript pay1of3; pay1of3.SetMultisig(1, keys);
 
-    txFrom.vout[0].scriptPubKey = payScriptHash1;
+    txFrom.vout[0].scriptPubKey.SetDestination(pay1.GetID()); // P2SH (OP_CHECKSIG)
     txFrom.vout[0].nValue = 1000;
-    txFrom.vout[1].scriptPubKey = pay1;
+    txFrom.vout[1].scriptPubKey = pay1; // ordinary OP_CHECKSIG
     txFrom.vout[1].nValue = 2000;
-    txFrom.vout[2].scriptPubKey = pay1of3;
+    txFrom.vout[2].scriptPubKey = pay1of3; // ordinary OP_CHECKMULTISIG
     txFrom.vout[2].nValue = 3000;
 
-    // Last three non-standard:
-    CScript empty;
-    keystore.AddCScript(empty);
-    txFrom.vout[3].scriptPubKey = empty;
+    // vout[3] is complicated 1-of-3 AND 2-of-3
+    // ... that is OK if wrapped in P2SH:
+    CScript oneAndTwo;
+    oneAndTwo << OP_1 << key[0].GetPubKey() << key[1].GetPubKey() << key[2].GetPubKey();
+    oneAndTwo << OP_3 << OP_CHECKMULTISIGVERIFY;
+    oneAndTwo << OP_2 << key[3].GetPubKey() << key[4].GetPubKey() << key[5].GetPubKey();
+    oneAndTwo << OP_3 << OP_CHECKMULTISIG;
+    keystore.AddCScript(oneAndTwo);
+    txFrom.vout[3].scriptPubKey.SetDestination(oneAndTwo.GetID());
     txFrom.vout[3].nValue = 4000;
-    // Can't use SetPayToScriptHash, it checks for the empty Script. So:
-    txFrom.vout[4].scriptPubKey << OP_HASH160 << Hash160(empty) << OP_EQUAL;
+
+    // vout[4] is max sigops:
+    CScript fifteenSigops; fifteenSigops << OP_1;
+    for (int i = 0; i < MAX_P2SH_SIGOPS; i++)
+        fifteenSigops << key[i%3].GetPubKey();
+    fifteenSigops << OP_15 << OP_CHECKMULTISIG;
+    keystore.AddCScript(fifteenSigops);
+    txFrom.vout[4].scriptPubKey.SetDestination(fifteenSigops.GetID());
     txFrom.vout[4].nValue = 5000;
-    CScript oneOfEleven;
-    oneOfEleven << OP_1;
-    for (int i = 0; i < 11; i++)
-        oneOfEleven << key[0].GetPubKey();
-    oneOfEleven << OP_11 << OP_CHECKMULTISIG;
-    txFrom.vout[5].scriptPubKey.SetDestination(oneOfEleven.GetID());
-    txFrom.vout[5].nValue = 6000;
+
+    // vout[5/6] are non-standard because they exceed MAX_P2SH_SIGOPS
+    CScript sixteenSigops; sixteenSigops << OP_16 << OP_CHECKMULTISIG;
+    keystore.AddCScript(sixteenSigops);
+    txFrom.vout[5].scriptPubKey.SetDestination(fifteenSigops.GetID());
+    txFrom.vout[5].nValue = 5000;
+    CScript twentySigops; twentySigops << OP_CHECKMULTISIG;
+    keystore.AddCScript(twentySigops);
+    txFrom.vout[6].scriptPubKey.SetDestination(twentySigops.GetID());
+    txFrom.vout[6].nValue = 6000;
+
 
     coins.SetCoins(txFrom.GetHash(), CCoins(txFrom, 0));
 
@@ -303,19 +318,24 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
     txTo.vout.resize(1);
     txTo.vout[0].scriptPubKey.SetDestination(key[1].GetPubKey().GetID());
 
-    txTo.vin.resize(3);
-    txTo.vin[0].prevout.n = 0;
-    txTo.vin[0].prevout.hash = txFrom.GetHash();
+    txTo.vin.resize(5);
+    for (int i = 0; i < 5; i++)
+    {
+        txTo.vin[i].prevout.n = i;
+        txTo.vin[i].prevout.hash = txFrom.GetHash();
+    }
     BOOST_CHECK(SignSignature(keystore, txFrom, txTo, 0));
-    txTo.vin[1].prevout.n = 1;
-    txTo.vin[1].prevout.hash = txFrom.GetHash();
     BOOST_CHECK(SignSignature(keystore, txFrom, txTo, 1));
-    txTo.vin[2].prevout.n = 2;
-    txTo.vin[2].prevout.hash = txFrom.GetHash();
     BOOST_CHECK(SignSignature(keystore, txFrom, txTo, 2));
+    // SignSignature doesn't know how to sign these. We're
+    // not testing validating signatures, so just create
+    // dummy signatures that DO include the correct P2SH scripts:
+    txTo.vin[3].scriptSig << OP_11 << OP_11 << static_cast<vector<unsigned char> >(oneAndTwo);
+    txTo.vin[4].scriptSig << static_cast<vector<unsigned char> >(fifteenSigops);
 
     BOOST_CHECK(::AreInputsStandard(txTo, coins));
-    BOOST_CHECK_EQUAL(GetP2SHSigOpCount(txTo, coins), 1U);
+    // 22 P2SH sigops for all inputs (1 for vin[0], 6 for vin[3], 15 for vin[4]
+    BOOST_CHECK_EQUAL(GetP2SHSigOpCount(txTo, coins), 22U);
 
     // Make sure adding crap to the scriptSigs makes them non-standard:
     for (int i = 0; i < 3; i++)
@@ -326,23 +346,29 @@ BOOST_AUTO_TEST_CASE(AreInputsStandard)
         txTo.vin[i].scriptSig = t;
     }
 
-    CMutableTransaction txToNonStd;
-    txToNonStd.vout.resize(1);
-    txToNonStd.vout[0].scriptPubKey.SetDestination(key[1].GetPubKey().GetID());
-    txToNonStd.vout[0].nValue = 1000;
-    txToNonStd.vin.resize(2);
-    txToNonStd.vin[0].prevout.n = 4;
-    txToNonStd.vin[0].prevout.hash = txFrom.GetHash();
-    txToNonStd.vin[0].scriptSig << Serialize(empty);
-    txToNonStd.vin[1].prevout.n = 5;
-    txToNonStd.vin[1].prevout.hash = txFrom.GetHash();
-    txToNonStd.vin[1].scriptSig << OP_0 << Serialize(oneOfEleven);
-
-    BOOST_CHECK(!::AreInputsStandard(txToNonStd, coins));
-    BOOST_CHECK_EQUAL(GetP2SHSigOpCount(txToNonStd, coins), 11U);
-
-    txToNonStd.vin[0].scriptSig.clear();
-    BOOST_CHECK(!::AreInputsStandard(txToNonStd, coins));
+    CMutableTransaction txToNonStd1;
+    txToNonStd1.vout.resize(1);
+    txToNonStd1.vout[0].scriptPubKey.SetDestination(key[1].GetPubKey().GetID());
+    txToNonStd1.vout[0].nValue = 1000;
+    txToNonStd1.vin.resize(1);
+    txToNonStd1.vin[0].prevout.n = 5;
+    txToNonStd1.vin[0].prevout.hash = txFrom.GetHash();
+    txToNonStd1.vin[0].scriptSig << static_cast<vector<unsigned char> >(sixteenSigops);
+
+    BOOST_CHECK(!::AreInputsStandard(txToNonStd1, coins));
+    BOOST_CHECK_EQUAL(GetP2SHSigOpCount(txToNonStd1, coins), 16U);
+
+    CMutableTransaction txToNonStd2;
+    txToNonStd2.vout.resize(1);
+    txToNonStd2.vout[0].scriptPubKey.SetDestination(key[1].GetPubKey().GetID());
+    txToNonStd2.vout[0].nValue = 1000;
+    txToNonStd2.vin.resize(1);
+    txToNonStd2.vin[0].prevout.n = 6;
+    txToNonStd2.vin[0].prevout.hash = txFrom.GetHash();
+    txToNonStd2.vin[0].scriptSig << static_cast<vector<unsigned char> >(twentySigops);
+
+    BOOST_CHECK(!::AreInputsStandard(txToNonStd2, coins));
+    BOOST_CHECK_EQUAL(GetP2SHSigOpCount(txToNonStd2, coins), 20U);
 }
 
 BOOST_AUTO_TEST_SUITE_END()