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.

2 files changed, 22 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;
     }
 
 
diff --git a/src/script.h b/src/script.h
index 26bb65a..d36a317 100644
--- a/src/script.h
+++ b/src/script.h
@@ -8,6 +8,15 @@ class CTransaction;
 // script evaluation allocates whatever the transaction asks it to.
 static const unsigned int MAX_SCRIPT_ELEMENT_SIZE = 520;
 
+// Bounds on what one script may do while being evaluated. The element cap
+// above limits how big a single item is; these limit how many there can be and
+// how much work producing them costs. Without them, a script 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, and every node that validates it pays.
+static const unsigned int MAX_OPS_PER_SCRIPT     = 201;
+static const unsigned int MAX_STACK_SIZE         = 1000;
+
 enum
 {
     SIGHASH_ALL = 1,