script: bound how many operations and stack entries a script may use (#57)

v1.2.1 disabled the unbounded opcodes and capped a single pushed element at
520 bytes. What it did not add was a ceiling on how many items there can be,
so a script still pays for itself once, in bytes, and then multiplies: 520
bytes per stack entry means a script of N bytes made almost entirely of
OP_DUP occupies roughly 520N in memory, on every node that validates it.

Two limits, both from Bitcoin:

  - at most 201 operations per script, counted outside the fExec test so
    the cost of a script cannot depend on which branch a signature happens
    to take. Pushes are exempt, being already bounded by the script length
    and by MAX_SCRIPT_ELEMENT_SIZE.
  - at most 1000 entries across both stacks together, counted together
    because OP_TOALTSTACK would otherwise move the problem rather than
    solve it.

This tightens validation, so a node that does not upgrade accepts a
superset of what this one accepts and is not stranded.

Verified against the live chain: a node with these rules synced all 3910
blocks from genesis and accepted every one, so nothing in use relies on
scripts these limits would reject.

1 files changed, 13 insertions, 0 deletions

diff --git a/src/script.cpp b/src/script.cpp
index 44eed93..6d4fb34 100644
--- a/src/script.cpp
+++ b/src/script.cpp
@@ -51,6 +51,7 @@ bool EvalScript(const CScript& script, const CTransaction& txTo, unsigned int nI
     vector<bool> vfExec;
     vector<valtype> stack;
     vector<valtype> altstack;
+    unsigned int nOpCount = 0;
     if (pvStackRet)
         pvStackRet->clear();
 
@@ -85,6 +86,13 @@ bool EvalScript(const CScript& script, const CTransaction& txTo, unsigned int nI
             opcode == OP_MOD   || opcode == OP_LSHIFT || opcode == OP_RSHIFT)
             return false;
 
+        // Counted outside fExec for the same reason: the cost of a script must
+        // not depend on which branch a signature happens to take. Pushes are
+        // exempt because their cost is already bounded by the script's own
+        // length and by MAX_SCRIPT_ELEMENT_SIZE.
+        if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT)
+            return false;
+
         if (fExec && opcode <= OP_PUSHDATA4)
             stack.push_back(vchPushValue);
         else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
@@ -824,6 +832,11 @@ bool EvalScript(const CScript& script, const CTransaction& txTo, unsigned int nI
             default:
                 return false;
         }
+
+        // Both stacks together, because OP_TOALTSTACK would otherwise move the
+        // problem rather than solve it.
+        if (stack.size() + altstack.size() > MAX_STACK_SIZE)
+            return false;
     }