ScriptInterpreter.js

require('classtool');

function spec(b) {
  var assert = require('assert');
  var config = b.config || require('./config');
  var log = b.log || require('./util/log');

  var Opcode = require('./Opcode').class();

  // Make opcodes available as pseudo-constants
  for (var i in Opcode.map) {
    eval(i + " = " + Opcode.map[i] + ";");
  }

  var bignum = b.bignum || require('bignum');
  var Util = b.Util || require('./util/util');
  var Script = require('./Script').class();

  function ScriptInterpreter() {
    this.stack = [];
    this.disableUnsafeOpcodes = true;
  };

  ScriptInterpreter.prototype.eval = function eval(script, tx, inIndex, hashType, callback)
  {
    if ("function" !== typeof callback) {
      throw new Error("ScriptInterpreter.eval() requires a callback");
    }

    var pc = 0;

    var execStack = [];
    var altStack = [];
    var hashStart = 0;
    var opCount = 0;

    if (script.buffer.length > 10000) {
      callback(new Error("Oversized script (> 10k bytes)"));
      return this;
    }

    // Start execution by running the first step
    executeStep.call(this, callback);

    function executeStep(cb) {
      // Once all chunks have been processed, execution ends
      if (pc >= script.chunks.length) {
        // Execution stack must be empty at the end of the script
        if (execStack.length) {
          cb(new Error("Execution stack ended non-empty"));
          return;
        }

        // Execution successful (Note that we still have to check whether the
        // final stack contains a truthy value.)
        cb(null);
        return;
      }

      try {
        // The execution bit is true if there are no "false" values in the
        // execution stack. (A "false" value indicates that we're in the
        // inactive branch of an if statement.)
        var exec = !~execStack.indexOf(false);

        var opcode = script.chunks[pc++];

        if (opcode.length > 520) {
          throw new Error("Max push value size exceeded (>520)");
        }

        if (opcode > OP_16 && ++opCount > 201) {
          throw new Error("Opcode limit exceeded (>200)");
        }

        if (this.disableUnsafeOpcodes &&
            "number" === typeof opcode &&
            (opcode === OP_CAT ||
             opcode === OP_SUBSTR ||
             opcode === OP_LEFT ||
             opcode === OP_RIGHT ||
             opcode === OP_INVERT ||
             opcode === OP_AND ||
             opcode === OP_OR ||
             opcode === OP_XOR ||
             opcode === OP_2MUL ||
             opcode === OP_2DIV ||
             opcode === OP_MUL ||
             opcode === OP_DIV ||
             opcode === OP_MOD ||
             opcode === OP_LSHIFT ||
             opcode === OP_RSHIFT)) {
          throw new Error("Encountered a disabled opcode");
        }

        if (exec && Buffer.isBuffer(opcode))
          this.stack.push(opcode);
        else if (exec || (OP_IF <= opcode && opcode <= OP_ENDIF))
        switch (opcode) {
        case OP_0:
          this.stack.push(new Buffer([]));
          break;

        case OP_1NEGATE:
        case OP_1:
        case OP_2:
        case OP_3:
        case OP_4:
        case OP_5:
        case OP_6:
        case OP_7:
        case OP_8:
        case OP_9:
        case OP_10:
        case OP_11:
        case OP_12:
        case OP_13:
        case OP_14:
        case OP_15:
        case OP_16:
          this.stack.push(bigintToBuffer(opcode - OP_1 + 1));
          break;

        case OP_NOP:
        case OP_NOP1: 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;

        case OP_IF:
        case OP_NOTIF:
          // <expression> if [statements] [else [statements]] endif
          var value = false;
          if (exec) {
            value = castBool(this.stackPop());
            if (opcode === OP_NOTIF) {
              value = !value;
            }
          }
          execStack.push(value);
          break;

        case OP_ELSE:
          if (execStack.length < 1) {
            throw new Error("Unmatched OP_ELSE");
          }
          execStack[execStack.length-1] = !execStack[execStack.length-1];
          break;

        case OP_ENDIF:
          if (execStack.length < 1) {
            throw new Error("Unmatched OP_ENDIF");
          }
          execStack.pop();
          break;

        case OP_VERIFY:
          var value = castBool(this.stackTop());
          if (value) {
            this.stackPop();
          } else {
            throw new Error("OP_VERIFY negative");
          }
          break;

        case OP_RETURN:
          throw new Error("OP_RETURN");

        case OP_TOALTSTACK:
          altStack.push(this.stackPop());
          break;

        case OP_FROMALTSTACK:
          if (altStack.length < 1) {
            throw new Error("OP_FROMALTSTACK with alt stack empty");
          }
          this.stack.push(altStack.pop());
          break;

        case OP_2DROP:
          // (x1 x2 -- )
          this.stackPop();
          this.stackPop();
          break;

        case OP_2DUP:
          // (x1 x2 -- x1 x2 x1 x2)
          var v1 = this.stackTop(2);
          var v2 = this.stackTop(1);
          this.stack.push(v1);
          this.stack.push(v2);
          break;

        case OP_3DUP:
          // (x1 x2 -- x1 x2 x1 x2)
          var v1 = this.stackTop(3);
          var v2 = this.stackTop(2);
          var v3 = this.stackTop(1);
          this.stack.push(v1);
          this.stack.push(v2);
          this.stack.push(v3);
          break;

        case OP_2OVER:
          // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
          var v1 = this.stackTop(4);
          var v2 = this.stackTop(3);
          this.stack.push(v1);
          this.stack.push(v2);
          break;

        case OP_2ROT:
          // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
          var v1 = this.stackTop(6);
          var v2 = this.stackTop(5);
          this.stack.splice(this.stack.length - 6, 2);
          this.stack.push(v1);
          this.stack.push(v2);
          break;

        case OP_2SWAP:
          // (x1 x2 x3 x4 -- x3 x4 x1 x2)
          this.stackSwap(4, 2);
          this.stackSwap(3, 1);
          break;

        case OP_IFDUP:
          // (x - 0 | x x)
          var value = this.stackTop();
          if (castBool(value)) {
            this.stack.push(value);
          }
          break;

        case OP_DEPTH:
          // -- stacksize
          var value = bignum(this.stack.length);
          this.stack.push(bigintToBuffer(value));
          break;

        case OP_DROP:
          // (x -- )
          this.stackPop();
          break;

        case OP_DUP:
          // (x -- x x)
          this.stack.push(this.stackTop());
          break;

        case OP_NIP:
          // (x1 x2 -- x2)
          if (this.stack.length < 2) {
            throw new Error("OP_NIP insufficient stack size");
          }
          this.stack.splice(this.stack.length - 2, 1);
          break;

        case OP_OVER:
          // (x1 x2 -- x1 x2 x1)
          this.stack.push(this.stackTop(2));
          break;

        case OP_PICK:
        case OP_ROLL:
          // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
          // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
          var n = castInt(this.stackPop());
          if (n < 0 || n >= this.stack.length) {
            throw new Error("OP_PICK/OP_ROLL insufficient stack size");
          }
          var value = this.stackTop(n+1);
          if (opcode === OP_ROLL) {
            this.stack.splice(this.stack.length - n - 1, 1);
          }
          this.stack.push(value);
          break;

        case OP_ROT:
          // (x1 x2 x3 -- x2 x3 x1)
          //  x2 x1 x3  after first swap
          //  x2 x3 x1  after second swap
          this.stackSwap(3, 2);
          this.stackSwap(2, 1);
          break;

        case OP_SWAP:
          // (x1 x2 -- x2 x1)
          this.stackSwap(2, 1);
          break;

        case OP_TUCK:
          // (x1 x2 -- x2 x1 x2)
          if (this.stack.length < 2) {
            throw new Error("OP_TUCK insufficient stack size");
          }
          this.stack.splice(this.stack.length - 2, 0, this.stackTop());
          break;

        case OP_CAT:
          // (x1 x2 -- out)
          var v1 = this.stackTop(2);
          var v2 = this.stackTop(1);
          this.stackPop();
          this.stackPop();
          this.stack.push(v1.concat(v2));
          break;

        case OP_SUBSTR:
          // (in begin size -- out)
          var buf = this.stackTop(3);
          var start = castInt(this.stackTop(2));
          var len = castInt(this.stackTop(1));
          if (start < 0 || len < 0) {
            throw new Error("OP_SUBSTR start < 0 or len < 0");
          }
          if ((start + len) >= buf.length) {
            throw new Error("OP_SUBSTR range out of bounds");
          }
          this.stackPop();
          this.stackPop();
          this.stack[this.stack.length-1] = buf.slice(start, start + len);
          break;

        case OP_LEFT:
        case OP_RIGHT:
          // (in size -- out)
          var buf = this.stackTop(2);
          var size = castInt(this.stackTop(1));
          if (size < 0) {
            throw new Error("OP_LEFT/OP_RIGHT size < 0");
          }
          if (size > buf.length) {
            size = buf.length;
          }
          this.stackPop();
          if (opcode === OP_LEFT) {
            this.stack[this.stack.length-1] = buf.slice(0, size);
          } else {
            this.stack[this.stack.length-1] = buf.slice(buf.length - size);
          }
          break;

        case OP_SIZE:
          // (in -- in size)
          var value = bignum(this.stackTop().length);
          this.stack.push(bigintToBuffer(value));
          break;

        case OP_INVERT:
          // (in - out)
          var buf = this.stackTop();
          for (var i = 0, l = buf.length; i < l; i++) {
            buf[i] = ~buf[i];
          }
          break;

        case OP_AND:
        case OP_OR:
        case OP_XOR:
          // (x1 x2 - out)
          var v1 = this.stackTop(2);
          var v2 = this.stackTop(1);
          this.stackPop();
          this.stackPop();
          var out = new Buffer(Math.max(v1.length, v2.length));
          if (opcode === OP_AND) {
            for (var i = 0, l = out.length; i < l; i++) {
              out[i] = v1[i] & v2[i];
            }
          } else if (opcode === OP_OR) {
            for (var i = 0, l = out.length; i < l; i++) {
              out[i] = v1[i] | v2[i];
            }
          } else if (opcode === OP_XOR) {
            for (var i = 0, l = out.length; i < l; i++) {
              out[i] = v1[i] ^ v2[i];
            }
          }
          this.stack.push(out);
          break;

        case OP_EQUAL:
        case OP_EQUALVERIFY:
        //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
          // (x1 x2 - bool)
          var v1 = this.stackTop(2);
          var v2 = this.stackTop(1);
          var value = v1.compare(v2) == 0;

          // OP_NOTEQUAL is disabled because it would be too easy to say
          // something like n != 1 and have some wiseguy pass in 1 with extra
          // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
          //if (opcode == OP_NOTEQUAL)
          //    fEqual = !fEqual;

          this.stackPop();
          this.stackPop();
          this.stack.push(new Buffer([value ? 1 : 0]));
          if (opcode === OP_EQUALVERIFY) {
            if (value) {
              this.stackPop();
            } else {
              throw new Error("OP_EQUALVERIFY negative");
            }
          }
          break;

        case OP_1ADD:
        case OP_1SUB:
        case OP_2MUL:
        case OP_2DIV:
        case OP_NEGATE:
        case OP_ABS:
        case OP_NOT:
        case OP_0NOTEQUAL:
          // (in -- out)
          var num = castBigint(this.stackTop());
          switch (opcode) {
          case OP_1ADD:      num = num.add(bignum(1)); break;
          case OP_1SUB:      num = num.sub(bignum(1)); break;
          case OP_2MUL:      num = num.mul(bignum(2)); break;
          case OP_2DIV:      num = num.div(bignum(2)); break;
          case OP_NEGATE:    num = num.neg(); break;
          case OP_ABS:       num = num.abs(); break;
          case OP_NOT:       num = bignum(num.cmp(0) == 0 ? 1 : 0); break;
          case OP_0NOTEQUAL: num = bignum(num.cmp(0) == 0 ? 0 : 1); break;
          }
          this.stack[this.stack.length-1] = bigintToBuffer(num);
          break;

        case OP_ADD:
        case OP_SUB:
        case OP_MUL:
        case OP_DIV:
        case OP_MOD:
        case OP_LSHIFT:
        case OP_RSHIFT:
        case OP_BOOLAND:
        case OP_BOOLOR:
        case OP_NUMEQUAL:
        case OP_NUMEQUALVERIFY:
        case OP_NUMNOTEQUAL:
        case OP_LESSTHAN:
        case OP_GREATERTHAN:
        case OP_LESSTHANOREQUAL:
        case OP_GREATERTHANOREQUAL:
        case OP_MIN:
        case OP_MAX:
          // (x1 x2 -- out)
          var v1 = castBigint(this.stackTop(2));
          var v2 = castBigint(this.stackTop(1));
          var num;
          switch (opcode) {
          case OP_ADD: num = v1.add(v2); break;
          case OP_SUB: num = v1.sub(v2); break;
          case OP_MUL: num = v1.mul(v2); break;
          case OP_DIV: num = v1.div(v2); break;
          case OP_MOD: num = v1.mod(v2); break;

          case OP_LSHIFT:
            if (v2.cmp(0) < 0 || v2.cmp(2048) > 0) {
              throw new Error("OP_LSHIFT parameter out of bounds");
            }
            num = v1.shiftLeft(v2);
            break;

          case OP_RSHIFT:
            if (v2.cmp(0) < 0 || v2.cmp(2048) > 0) {
              throw new Error("OP_RSHIFT parameter out of bounds");
            }
            num = v1.shiftRight(v2);
            break;

          case OP_BOOLAND:
            num = bignum((v1.cmp(0) != 0 && v2.cmp(0) != 0) ? 1 : 0);
            break;

          case OP_BOOLOR:
            num = bignum((v1.cmp(0) != 0 || v2.cmp(0) != 0) ? 1 : 0);
            break;

          case OP_NUMEQUAL:
          case OP_NUMEQUALVERIFY:
            num = bignum(v1.cmp(v2) == 0 ? 1 : 0);
            break;

          case OP_NUMNOTEQUAL:;
            num = bignum(v1.cmp(v2) != 0 ? 1 : 0);
            break;

          case OP_LESSTHAN:
            num = bignum(v1.lt(v2) ? 1 : 0);
            break;

          case OP_GREATERTHAN:
            num = bignum(v1.gt(v2) ? 1 : 0);
            break;

          case OP_LESSTHANOREQUAL:
            num = bignum(v1.gt(v2) ? 0 : 1);
            break;

          case OP_GREATERTHANOREQUAL:
            num = bignum(v1.lt(v2) ? 0 : 1);
            break;

          case OP_MIN: num = (v1.lt(v2) ? v1 : v2); break;
          case OP_MAX: num = (v1.gt(v2) ? v1 : v2); break;
          }
          this.stackPop();
          this.stackPop();
          this.stack.push(bigintToBuffer(num));

          if (opcode === OP_NUMEQUALVERIFY) {
            if (castBool(this.stackTop())) {
              this.stackPop();
            } else {
              throw new Error("OP_NUMEQUALVERIFY negative");
            }
          }
          break;

        case OP_WITHIN:
          // (x min max -- out)
          var v1 = castBigint(this.stackTop(3));
          var v2 = castBigint(this.stackTop(2));
          var v3 = castBigint(this.stackTop(1));
          this.stackPop();
          this.stackPop();
          this.stackPop();
          var value = v1.cmp(v2) >= 0 && v1.cmp(v3) < 0;
          this.stack.push(bigintToBuffer(value ? 1 : 0));
          break;

        case OP_RIPEMD160:
        case OP_SHA1:
        case OP_SHA256:
        case OP_HASH160:
        case OP_HASH256:
          // (in -- hash)
          var value = this.stackPop();
          var hash;
          if (opcode === OP_RIPEMD160) {
            hash = Util.ripe160(value);
          } else if (opcode === OP_SHA1) {
            hash = Util.sha1(value);
          } else if (opcode === OP_SHA256) {
            hash = Util.sha256(value);
          } else if (opcode === OP_HASH160) {
            hash = Util.sha256ripe160(value);
          } else if (opcode === OP_HASH256) {
            hash = Util.twoSha256(value);
          }
          this.stack.push(hash);
          break;

        case OP_CODESEPARATOR:
          // Hash starts after the code separator
          hashStart = pc;
          break;

        case OP_CHECKSIG:
        case OP_CHECKSIGVERIFY:
          // (sig pubkey -- bool)
          var sig = this.stackTop(2);
          var pubkey = this.stackTop(1);

          // Get the part of this script since the last OP_CODESEPARATOR
          var scriptChunks = script.chunks.slice(hashStart);

          // Convert to binary
          var scriptCode = Script.fromChunks(scriptChunks);

          // Remove signature if present (a signature can't sign itself)
          scriptCode.findAndDelete(sig);

          // Verify signature
          checkSig(sig, pubkey, scriptCode, tx, inIndex, hashType, function (e, result) {
            try {
              var success;

              if (e) {
                // We intentionally ignore errors during signature verification and
                // treat these cases as an invalid signature.
                success = false;
              } else {
                success = result;
              }

              // Update stack
              this.stackPop();
              this.stackPop();
              this.stack.push(new Buffer([success ? 1 : 0]));
              if (opcode === OP_CHECKSIGVERIFY) {
                if (success) {
                  this.stackPop();
                } else {
                  throw new Error("OP_CHECKSIGVERIFY negative");
                }
              }

              // Run next step
              executeStep.call(this, cb);
            } catch(e) {
              cb(e);
            }
          }.bind(this));

          // Note that for asynchronous opcodes we have to return here to prevent
          // the next opcode from being executed.
          return;

        case OP_CHECKMULTISIG:
        case OP_CHECKMULTISIGVERIFY:
          // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
          var keysCount = castInt(this.stackPop());
          if (keysCount < 0 || keysCount > 20) {
            throw new Error("OP_CHECKMULTISIG keysCount out of bounds");
          }
          opCount += keysCount;
          if (opCount > 201) {
            throw new Error("Opcode limit exceeded (>200)");
          }
          var keys = [];
          for (var i = 0, l = keysCount; i < l; i++) {
            keys.push(this.stackPop());
          }
          var sigsCount = castInt(this.stackPop());
          if (sigsCount < 0 || sigsCount > keysCount) {
            throw new Error("OP_CHECKMULTISIG sigsCount out of bounds");
          }
          var sigs = [];
          for (var i = 0, l = sigsCount; i < l; i++) {
            sigs.push(this.stackPop());
          }

          // The original client has a bug where it pops an extra element off the
          // stack. It can't be fixed without causing a chain split and we need to
          // imitate this behavior as well.
          this.stackPop();

          // Get the part of this script since the last OP_CODESEPARATOR
          var scriptChunks = script.chunks.slice(hashStart);

          // Convert to binary
          var scriptCode = Script.fromChunks(scriptChunks);

          // Drop the signatures, since a signature can't sign itself
          sigs.forEach(function (sig) {
            scriptCode.findAndDelete(sig);
          });

          var success = true, isig = 0, ikey = 0;
          checkMultiSigStep.call(this);

          function checkMultiSigStep() {
            try {
              if (success && sigsCount > 0) {
                var sig = sigs[isig];
                var key = keys[ikey];

                checkSig(sig, key, scriptCode, tx, inIndex, hashType, function (e, result) {
                  try {
                    if (!e && result) {
                      isig++;
                      sigsCount--;
                    } else {
                      ikey++;
                      keysCount--;

                      // If there are more signatures than keys left, then too many
                      // signatures have failed
                      if (sigsCount > keysCount) {
                        success = false;
                      }
                    }

                    checkMultiSigStep.call(this);
                  } catch (e) {
                    cb(e);
                  }
                }.bind(this));
              } else {
                this.stack.push(new Buffer([success ? 1 : 0]));
                if (opcode === OP_CHECKMULTISIGVERIFY) {
                  if (success) {
                    this.stackPop();
                  } else {
                    throw new Error("OP_CHECKMULTISIGVERIFY negative");
                  }
                }

                // Run next step
                executeStep.call(this, cb);
              }
            } catch(e) {
              cb(e);
            }
          };

          // Note that for asynchronous opcodes we have to return here to prevent
          // the next opcode from being executed.
          return;

        default:
          throw new Error("Unknown opcode encountered");
        }

        // Size limits
        if ((this.stack.length + altStack.length) > 1000) {
          throw new Error("Maximum stack size exceeded");
        }

        // Run next step
        if (pc % 100) {
          // V8 allows for much deeper stacks than Bitcoin's scripting language,
          // but just to be safe, we'll reset the stack every 100 steps
          process.nextTick(executeStep.bind(this, cb));
        } else {
          executeStep.call(this, cb);
        }
      } catch (e) {
        log.debug("Script aborted: "+
                      (e.message ? e : e));
        cb(e);
      }
    }
  };

  ScriptInterpreter.prototype.evalTwo =
  function evalTwo(scriptSig, scriptPubkey, tx, n, hashType, callback)
  {
    var self = this;

    self.eval(scriptSig, tx, n, hashType, function (e) {
      if (e) {
        callback(e)
        return;
      }

      self.eval(scriptPubkey, tx, n, hashType, callback);
    });
  };

  /**
   * Get the top element of the stack.
   *
   * Using the offset parameter this function can also access lower elements
   * from the stack.
   */
  ScriptInterpreter.prototype.stackTop = function stackTop(offset) {
    offset = +offset || 1;
    if (offset < 1) offset = 1;

    if (offset > this.stack.length) {
      throw new Error('ScriptInterpreter.stackTop(): Stack underrun');
    }

    return this.stack[this.stack.length-offset];
  };

  ScriptInterpreter.prototype.stackBack = function stackBack() 
  {
    return this.stack[-1];
  };

  /**
   * Pop the top element off the stack and return it.
   */
  ScriptInterpreter.prototype.stackPop = function stackPop() {
    if (this.stack.length < 1) {
      throw new Error('ScriptInterpreter.stackTop(): Stack underrun');
    }

    return this.stack.pop();
  };

  ScriptInterpreter.prototype.stackSwap = function stackSwap(a, b) {
    if (this.stack.length < a || this.stack.length < b) {
      throw new Error('ScriptInterpreter.stackTop(): Stack underrun');
    }

    var s = this.stack,
        l = s.length;

    var tmp = s[l - a];
    s[l - a] = s[l - b];
    s[l - b] = tmp;
  };

  /**
   * Returns a version of the stack with only primitive types.
   *
   * The return value is an array. Any single byte buffer is converted to an
   * integer. Any longer Buffer is converted to a hex string.
   */
  ScriptInterpreter.prototype.getPrimitiveStack = function getPrimitiveStack() {
    return this.stack.map(function (entry) {
      if (entry.length > 2) {
        return entry.slice(0).toHex();
      }
      var num = castBigint(entry);
      if (num.cmp(-128) >= 0 && num.cmp(127) <= 0) {
        return num.toNumber();
      } else {
        return entry.slice(0).toHex();
      }
    });
  };

  var castBool = ScriptInterpreter.castBool = function castBool(v) {
    for (var i = 0, l = v.length; i < l; i++) {
      if (v[i] != 0) {
        // Negative zero is still zero
        if (i == (l-1) && v[i] == 0x80) {
          return false;
        }
        return true;
      }
    }
    return false;
  };
  var castInt = ScriptInterpreter.castInt = function castInt(v) {
    return castBigint(v).toNumber();
  };
  var castBigint = ScriptInterpreter.castBigint = function castBigint(v) {
    if (!v.length) {
      return bignum(0);
    }

    // Arithmetic operands must be in range [-2^31...2^31]
    if (v.length > 4) {
      throw new Error("Bigint cast overflow (> 4 bytes)");
    }

    var w = new Buffer(v.length);
    v.copy(w);
    w.reverse();
    if (w[0] & 0x80) {
      w[0] &= 0x7f;
      return bignum.fromBuffer(w).neg();
    } else {
      // Positive number
      return bignum.fromBuffer(w);
    }
  };
  var bigintToBuffer = ScriptInterpreter.bigintToBuffer = function bigintToBuffer(v) {
    if ("number" === typeof v) {
      v = bignum(v);
    }

    var b,c;

    var cmp = v.cmp(0);
    if (cmp > 0) {
      b = v.toBuffer();
      if (b[0] & 0x80) {
        c = new Buffer(b.length + 1);
        b.copy(c, 1);
        c[0] = 0;
        return c.reverse();
      } else {
        return b.reverse();
      }
    } else if (cmp == 0) {
      return new Buffer([]);
    } else {
      b = v.neg().toBuffer();
      if (b[0] & 0x80) {
        c = new Buffer(b.length + 1);
        b.copy(c, 1);
        c[0] = 0x80;
        return c.reverse();
      } else {
        b[0] |= 0x80;
        return b.reverse();
      }
    }
  };

  ScriptInterpreter.prototype.getResult = function getResult() {
    if (this.stack.length === 0) {
      throw new Error("Empty stack after script evaluation");
    }

    return castBool(this.stack[this.stack.length-1]);
  };

  ScriptInterpreter.verify =
  function verify(scriptSig, scriptPubKey, txTo, n, hashType, callback)
  {
    if ("function" !== typeof callback) {
      throw new Error("ScriptInterpreter.verify() requires a callback");
    }

    // Create execution environment
    var si = new ScriptInterpreter();

    // Evaluate scripts
    si.evalTwo(scriptSig, scriptPubKey, txTo, n, hashType, function (err) {
      if (err) {
        callback(err);
        return;
      }

      // Cast result to bool
      try {
        var result = si.getResult();
      } catch (err) {
        callback(err);
        return;
      }

      callback(null, result);
    });

    return si;
  };

  function verifyStep4(scriptSig, scriptPubKey, txTo, nIn,
		       hashType, opts, callback, si, siCopy)
  {
	if (siCopy.stack.length == 0) {
		callback(null, false);
		return;
	}
	
	callback(null, castBool(siCopy.stackBack()));
  }

  function verifyStep3(scriptSig, scriptPubKey, txTo, nIn,
		       hashType, opts, callback, si, siCopy)
  {
	if (si.stack.length == 0) {
		callback(null, false);
		return;
	}
  	if (castBool(si.stackBack()) == false) {
		callback(null, false);
		return;
	}

	// if not P2SH, we're done
	if (!opts.verifyP2SH || !scriptPubKey.isP2SH()) {
		callback(null, true);
		return;
	}

	if (!scriptSig.isPushOnly()) {
		callback(null, false);
		return;
	}

	assert.notEqual(siCopy.length, 0);

	var subscript = new Script(siCopy.stackPop());

	ok = true;
	siCopy.eval(subscript, txTo, nIn, hashType, function (err) {
		if (err)
			callback(err);
		else
			verifyStep4(scriptSig, scriptPubKey, txTo, nIn,
				    hashType, opts, callback, si, siCopy);
	});
  }

  function verifyStep2(scriptSig, scriptPubKey, txTo, nIn,
		       hashType, opts, callback, si, siCopy)
  {
	if (opts.verifyP2SH) {
		si.stack.forEach(function(item) {
			siCopy.stack.push(item);
		});
	}

	si.eval(scriptPubKey, txTo, nIn, hashType, function (err) {
		if (err)
			callback(err);
		else
			verifyStep3(scriptSig, scriptPubKey, txTo, nIn,
				    hashType, opts, callback, si, siCopy);
	});
  }

  ScriptInterpreter.verifyFull =
  function verifyFull(scriptSig, scriptPubKey, txTo, nIn, hashType,
  		      opts, callback)
  {
  	var si = new ScriptInterpreter();
  	var siCopy = new ScriptInterpreter();

	si.eval(scriptSig, txTo, nIn, hashType, function (err) {
		if (err)
			callback(err);
		else
			verifyStep2(scriptSig, scriptPubKey, txTo, nIn,
				    hashType, opts, callback, si, siCopy);
	});
  };

  var checkSig = ScriptInterpreter.checkSig =
  function (sig, pubkey, scriptCode, tx, n, hashType, callback) {
    if (!sig.length) {
      callback(null, false);
      return;
    }

    if (hashType == 0) {
      hashType = sig[sig.length -1];
    } else if (hashType != sig[sig.length -1]) {
      callback(null, false);
      return;
    }
    sig = sig.slice(0, sig.length-1);

    try {
      // Signature verification requires a special hash procedure
      var hash = tx.hashForSignature(scriptCode, n, hashType);

      // Verify signature
      var key = new Util.BitcoinKey();
      key.public = pubkey;
      key.verifySignature(hash, sig, callback);
    } catch (err) {
      callback(null, false);
    }
  };

  return ScriptInterpreter;
};
module.defineClass(spec);