Merge pull request #5065

16d78bd Add valid invert of invalid every numeric opcode tests (Peter Todd)
2b62e17 Clearly separate PUSHDATA and numeric argument MINIMALDATA tests (Peter Todd)
dfeec18 Test every numeric-accepting opcode for correct handling of the numeric minimal encoding rule (Peter Todd)
554147a Ensure MINIMALDATA invalid tests can only fail one way (Peter Todd)
6004e77 Improve CScriptNum() comment (Peter Todd)
698c6ab Add SCRIPT_VERIFY_MINIMALDATA (BIP62 rules 3 and 4) (Pieter Wuille)
d752ba8 Add SCRIPT_VERIFY_SIGPUSHONLY (BIP62 rule 2) (Pieter Wuille)

5 files changed, 84 insertions, 48 deletions

diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index cd73b88210..11c909472a 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -157,6 +157,29 @@ bool static CheckPubKeyEncoding(const valtype &vchSig, unsigned int flags) {
     return true;
 }
 
+bool static CheckMinimalPush(const valtype& data, opcodetype opcode) {
+    if (data.size() == 0) {
+        // Could have used OP_0.
+        return opcode == OP_0;
+    } else if (data.size() == 1 && data[0] >= 1 && data[0] <= 16) {
+        // Could have used OP_1 .. OP_16.
+        return opcode == OP_1 + (data[0] - 1);
+    } else if (data.size() == 1 && data[0] == 0x81) {
+        // Could have used OP_1NEGATE.
+        return opcode == OP_1NEGATE;
+    } else if (data.size() <= 75) {
+        // Could have used a direct push (opcode indicating number of bytes pushed + those bytes).
+        return opcode == data.size();
+    } else if (data.size() <= 255) {
+        // Could have used OP_PUSHDATA.
+        return opcode == OP_PUSHDATA1;
+    } else if (data.size() <= 65535) {
+        // Could have used OP_PUSHDATA2.
+        return opcode == OP_PUSHDATA2;
+    }
+    return true;
+}
+
 bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker)
 {
     CScript::const_iterator pc = script.begin();
@@ -169,6 +192,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
     if (script.size() > 10000)
         return false;
     int nOpCount = 0;
+    bool fRequireMinimal = (flags & SCRIPT_VERIFY_MINIMALDATA) != 0;
 
     try
     {
@@ -205,9 +229,12 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                 opcode == OP_RSHIFT)
                 return false; // Disabled opcodes.
 
-            if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4)
+            if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4) {
+                if (fRequireMinimal && !CheckMinimalPush(vchPushValue, opcode)) {
+                    return false;
+                }
                 stack.push_back(vchPushValue);
-            else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
+            } else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
             switch (opcode)
             {
                 //
@@ -234,6 +261,8 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                     // ( -- value)
                     CScriptNum bn((int)opcode - (int)(OP_1 - 1));
                     stack.push_back(bn.getvch());
+                    // The result of these opcodes should always be the minimal way to push the data
+                    // they push, so no need for a CheckMinimalPush here.
                 }
                 break;
 
@@ -458,7 +487,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
                     if (stack.size() < 2)
                         return false;
-                    int n = CScriptNum(stacktop(-1)).getint();
+                    int n = CScriptNum(stacktop(-1), fRequireMinimal).getint();
                     popstack(stack);
                     if (n < 0 || n >= (int)stack.size())
                         return false;
@@ -557,7 +586,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                     // (in -- out)
                     if (stack.size() < 1)
                         return false;
-                    CScriptNum bn(stacktop(-1));
+                    CScriptNum bn(stacktop(-1), fRequireMinimal);
                     switch (opcode)
                     {
                     case OP_1ADD:       bn += bnOne; break;
@@ -590,8 +619,8 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                     // (x1 x2 -- out)
                     if (stack.size() < 2)
                         return false;
-                    CScriptNum bn1(stacktop(-2));
-                    CScriptNum bn2(stacktop(-1));
+                    CScriptNum bn1(stacktop(-2), fRequireMinimal);
+                    CScriptNum bn2(stacktop(-1), fRequireMinimal);
                     CScriptNum bn(0);
                     switch (opcode)
                     {
@@ -635,9 +664,9 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                     // (x min max -- out)
                     if (stack.size() < 3)
                         return false;
-                    CScriptNum bn1(stacktop(-3));
-                    CScriptNum bn2(stacktop(-2));
-                    CScriptNum bn3(stacktop(-1));
+                    CScriptNum bn1(stacktop(-3), fRequireMinimal);
+                    CScriptNum bn2(stacktop(-2), fRequireMinimal);
+                    CScriptNum bn3(stacktop(-1), fRequireMinimal);
                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
                     popstack(stack);
                     popstack(stack);
@@ -727,7 +756,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                     if ((int)stack.size() < i)
                         return false;
 
-                    int nKeysCount = CScriptNum(stacktop(-i)).getint();
+                    int nKeysCount = CScriptNum(stacktop(-i), fRequireMinimal).getint();
                     if (nKeysCount < 0 || nKeysCount > 20)
                         return false;
                     nOpCount += nKeysCount;
@@ -738,7 +767,7 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un
                     if ((int)stack.size() < i)
                         return false;
 
-                    int nSigsCount = CScriptNum(stacktop(-i)).getint();
+                    int nSigsCount = CScriptNum(stacktop(-i), fRequireMinimal).getint();
                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
                         return false;
                     int isig = ++i;
@@ -980,6 +1009,10 @@ bool SignatureChecker::CheckSig(const vector<unsigned char>& vchSigIn, const vec
 
 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, unsigned int flags, const BaseSignatureChecker& checker)
 {
+    if ((flags & SCRIPT_VERIFY_SIGPUSHONLY) != 0 && !scriptSig.IsPushOnly()) {
+        return false;
+    }
+
     vector<vector<unsigned char> > stack, stackCopy;
     if (!EvalScript(stack, scriptSig, flags, checker))
         return false;
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index de5ce2ced1..5133c80aab 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -46,6 +46,16 @@ enum
 
     // verify dummy stack item consumed by CHECKMULTISIG is of zero-length (softfork safe, BIP62 rule 7).
     SCRIPT_VERIFY_NULLDUMMY = (1U << 4),
+
+    // Using a non-push operator in the scriptSig causes script failure (softfork safe, BIP62 rule 2).
+    SCRIPT_VERIFY_SIGPUSHONLY = (1U << 5),
+
+    // Require minimal encodings for all push operations (OP_0... OP_16, OP_1NEGATE where possible, direct
+    // pushes up to 75 bytes, OP_PUSHDATA up to 255 bytes, OP_PUSHDATA2 for anything larger). Evaluating
+    // any other push causes the script to fail (BIP62 rule 3).
+    // In addition, whenever a stack element is interpreted as a number, it must be of minimal length (BIP62 rule 4).
+    // (softfork safe)
+    SCRIPT_VERIFY_MINIMALDATA = (1U << 6)
 };
 
 uint256 SignatureHash(const CScript &scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType);
diff --git a/src/script/script.cpp b/src/script/script.cpp
index 3e19d0c2bf..b879d72d6b 100644
--- a/src/script/script.cpp
+++ b/src/script/script.cpp
@@ -12,7 +12,7 @@ namespace {
 inline std::string ValueString(const std::vector<unsigned char>& vch)
 {
     if (vch.size() <= 4)
-        return strprintf("%d", CScriptNum(vch).getint());
+        return strprintf("%d", CScriptNum(vch, false).getint());
     else
         return HexStr(vch);
 }
@@ -230,7 +230,7 @@ bool CScript::IsPushOnly() const
             return false;
         // Note that IsPushOnly() *does* consider OP_RESERVED to be a
         // push-type opcode, however execution of OP_RESERVED fails, so
-        // it's not relevant to P2SH as the scriptSig would fail prior to
+        // it's not relevant to P2SH/BIP62 as the scriptSig would fail prior to
         // the P2SH special validation code being executed.
         if (opcode > OP_16)
             return false;
@@ -238,33 +238,6 @@ bool CScript::IsPushOnly() const
     return true;
 }
 
-bool CScript::HasCanonicalPushes() const
-{
-    const_iterator pc = begin();
-    while (pc < end())
-    {
-        opcodetype opcode;
-        std::vector<unsigned char> data;
-        if (!GetOp(pc, opcode, data))
-            return false;
-        if (opcode > OP_16)
-            continue;
-        if (opcode < OP_PUSHDATA1 && opcode > OP_0 && (data.size() == 1 && data[0] <= 16))
-            // Could have used an OP_n code, rather than a 1-byte push.
-            return false;
-        if (opcode == OP_PUSHDATA1 && data.size() < OP_PUSHDATA1)
-            // Could have used a normal n-byte push, rather than OP_PUSHDATA1.
-            return false;
-        if (opcode == OP_PUSHDATA2 && data.size() <= 0xFF)
-            // Could have used an OP_PUSHDATA1.
-            return false;
-        if (opcode == OP_PUSHDATA4 && data.size() <= 0xFFFF)
-            // Could have used an OP_PUSHDATA2.
-            return false;
-    }
-    return true;
-}
-
 std::string CScript::ToString() const
 {
     std::string str;
diff --git a/src/script/script.h b/src/script/script.h
index d450db5cad..05f2e7e3a9 100644
--- a/src/script/script.h
+++ b/src/script/script.h
@@ -192,10 +192,29 @@ public:
         m_value = n;
     }
 
-    explicit CScriptNum(const std::vector<unsigned char>& vch)
+    explicit CScriptNum(const std::vector<unsigned char>& vch, bool fRequireMinimal)
     {
-        if (vch.size() > nMaxNumSize)
-            throw scriptnum_error("CScriptNum(const std::vector<unsigned char>&) : overflow");
+        if (vch.size() > nMaxNumSize) {
+            throw scriptnum_error("script number overflow");
+        }
+        if (fRequireMinimal && vch.size() > 0) {
+            // Check that the number is encoded with the minimum possible
+            // number of bytes.
+            //
+            // If the most-significant-byte - excluding the sign bit - is zero
+            // then we're not minimal. Note how this test also rejects the
+            // negative-zero encoding, 0x80.
+            if ((vch.back() & 0x7f) == 0) {
+                // One exception: if there's more than one byte and the most
+                // significant bit of the second-most-significant-byte is set
+                // it would conflict with the sign bit. An example of this case
+                // is +-255, which encode to 0xff00 and 0xff80 respectively.
+                // (big-endian).
+                if (vch.size() <= 1 || (vch[vch.size() - 2] & 0x80) == 0) {
+                    throw scriptnum_error("non-minimally encoded script number");
+                }
+            }
+        }
         m_value = set_vch(vch);
     }
 
@@ -319,7 +338,6 @@ private:
     int64_t m_value;
 };
 
-
 /** Serialized script, used inside transaction inputs and outputs */
 class CScript : public std::vector<unsigned char>
 {
@@ -330,6 +348,10 @@ protected:
         {
             push_back(n + (OP_1 - 1));
         }
+        else if (n == 0)
+        {
+            push_back(OP_0);
+        }
         else
         {
             *this << CScriptNum::serialize(n);
@@ -551,12 +573,9 @@ public:
 
     bool IsPayToScriptHash() const;
 
-    // Called by IsStandardTx and P2SH VerifyScript (which makes it consensus-critical).
+    // Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical).
     bool IsPushOnly() const;
 
-    // Called by IsStandardTx.
-    bool HasCanonicalPushes() const;
-
     // Returns whether the script is guaranteed to fail at execution,
     // regardless of the initial stack. This allows outputs to be pruned
     // instantly when entering the UTXO set.
diff --git a/src/script/standard.h b/src/script/standard.h
index 961b214c89..248b941a64 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -41,6 +41,7 @@ static const unsigned int MANDATORY_SCRIPT_VERIFY_FLAGS = SCRIPT_VERIFY_P2SH;
 // blocks and we must accept those blocks.
 static const unsigned int STANDARD_SCRIPT_VERIFY_FLAGS = MANDATORY_SCRIPT_VERIFY_FLAGS |
                                                          SCRIPT_VERIFY_STRICTENC |
+                                                         SCRIPT_VERIFY_MINIMALDATA |
                                                          SCRIPT_VERIFY_NULLDUMMY;
 
 // For convenience, standard but not mandatory verify flags.