Back to home page

Bitcoin sources

 
 

    


File indexing completed on 2020-06-26 05:30:42

0001 // Copyright (c) 2009-2010 Satoshi Nakamoto
0002 // Copyright (c) 2009-2014 The Bitcoin developers
0003 // Distributed under the MIT software license, see the accompanying
0004 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
0005 
0006 #include "interpreter.h"
0007 
0008 #include "primitives/transaction.h"
0009 #include "crypto/ripemd160.h"
0010 #include "crypto/sha1.h"
0011 #include "crypto/sha256.h"
0012 #include "eccryptoverify.h"
0013 #include "pubkey.h"
0014 #include "script/script.h"
0015 #include "uint256.h"
0016 
0017 using namespace std;
0018 
0019 typedef vector<unsigned char> valtype;
0020 
0021 namespace {
0022 
0023 inline bool set_success(ScriptError* ret)
0024 {
0025     if (ret)
0026         *ret = SCRIPT_ERR_OK;
0027     return true;
0028 }
0029 
0030 inline bool set_error(ScriptError* ret, const ScriptError serror)
0031 {
0032     if (ret)
0033         *ret = serror;
0034     return false;
0035 }
0036 
0037 } // anon namespace
0038 
0039 bool CastToBool(const valtype& vch)
0040 {
0041     for (unsigned int i = 0; i < vch.size(); i++)
0042     {
0043         if (vch[i] != 0)
0044         {
0045             // Can be negative zero
0046             if (i == vch.size()-1 && vch[i] == 0x80)
0047                 return false;
0048             return true;
0049         }
0050     }
0051     return false;
0052 }
0053 
0054 /**
0055  * Script is a stack machine (like Forth) that evaluates a predicate
0056  * returning a bool indicating valid or not.  There are no loops.
0057  */
0058 #define stacktop(i)  (stack.at(stack.size()+(i)))
0059 #define altstacktop(i)  (altstack.at(altstack.size()+(i)))
0060 static inline void popstack(vector<valtype>& stack)
0061 {
0062     if (stack.empty())
0063         throw runtime_error("popstack() : stack empty");
0064     stack.pop_back();
0065 }
0066 
0067 bool static IsCompressedOrUncompressedPubKey(const valtype &vchPubKey) {
0068     if (vchPubKey.size() < 33) {
0069         //  Non-canonical public key: too short
0070         return false;
0071     }
0072     if (vchPubKey[0] == 0x04) {
0073         if (vchPubKey.size() != 65) {
0074             //  Non-canonical public key: invalid length for uncompressed key
0075             return false;
0076         }
0077     } else if (vchPubKey[0] == 0x02 || vchPubKey[0] == 0x03) {
0078         if (vchPubKey.size() != 33) {
0079             //  Non-canonical public key: invalid length for compressed key
0080             return false;
0081         }
0082     } else {
0083           //  Non-canonical public key: neither compressed nor uncompressed
0084           return false;
0085     }
0086     return true;
0087 }
0088 
0089 /**
0090  * A canonical signature exists of: <30> <total len> <02> <len R> <R> <02> <len S> <S> <hashtype>
0091  * Where R and S are not negative (their first byte has its highest bit not set), and not
0092  * excessively padded (do not start with a 0 byte, unless an otherwise negative number follows,
0093  * in which case a single 0 byte is necessary and even required).
0094  * 
0095  * See https://bitcointalk.org/index.php?topic=8392.msg127623#msg127623
0096  *
0097  * This function is consensus-critical since BIP66.
0098  */
0099 bool static IsValidSignatureEncoding(const std::vector<unsigned char> &sig) {
0100     // Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]
0101     // * total-length: 1-byte length descriptor of everything that follows,
0102     //   excluding the sighash byte.
0103     // * R-length: 1-byte length descriptor of the R value that follows.
0104     // * R: arbitrary-length big-endian encoded R value. It must use the shortest
0105     //   possible encoding for a positive integers (which means no null bytes at
0106     //   the start, except a single one when the next byte has its highest bit set).
0107     // * S-length: 1-byte length descriptor of the S value that follows.
0108     // * S: arbitrary-length big-endian encoded S value. The same rules apply.
0109     // * sighash: 1-byte value indicating what data is hashed (not part of the DER
0110     //   signature)
0111 
0112     // Minimum and maximum size constraints.
0113     if (sig.size() < 9) return false;
0114     if (sig.size() > 73) return false;
0115 
0116     // A signature is of type 0x30 (compound).
0117     if (sig[0] != 0x30) return false;
0118 
0119     // Make sure the length covers the entire signature.
0120     if (sig[1] != sig.size() - 3) return false;
0121 
0122     // Extract the length of the R element.
0123     unsigned int lenR = sig[3];
0124 
0125     // Make sure the length of the S element is still inside the signature.
0126     if (5 + lenR >= sig.size()) return false;
0127 
0128     // Extract the length of the S element.
0129     unsigned int lenS = sig[5 + lenR];
0130 
0131     // Verify that the length of the signature matches the sum of the length
0132     // of the elements.
0133     if ((size_t)(lenR + lenS + 7) != sig.size()) return false;
0134  
0135     // Check whether the R element is an integer.
0136     if (sig[2] != 0x02) return false;
0137 
0138     // Zero-length integers are not allowed for R.
0139     if (lenR == 0) return false;
0140 
0141     // Negative numbers are not allowed for R.
0142     if (sig[4] & 0x80) return false;
0143 
0144     // Null bytes at the start of R are not allowed, unless R would
0145     // otherwise be interpreted as a negative number.
0146     if (lenR > 1 && (sig[4] == 0x00) && !(sig[5] & 0x80)) return false;
0147 
0148     // Check whether the S element is an integer.
0149     if (sig[lenR + 4] != 0x02) return false;
0150 
0151     // Zero-length integers are not allowed for S.
0152     if (lenS == 0) return false;
0153 
0154     // Negative numbers are not allowed for S.
0155     if (sig[lenR + 6] & 0x80) return false;
0156 
0157     // Null bytes at the start of S are not allowed, unless S would otherwise be
0158     // interpreted as a negative number.
0159     if (lenS > 1 && (sig[lenR + 6] == 0x00) && !(sig[lenR + 7] & 0x80)) return false;
0160 
0161     return true;
0162 }
0163 
0164 bool static IsLowDERSignature(const valtype &vchSig, ScriptError* serror) {
0165     if (!IsValidSignatureEncoding(vchSig)) {
0166         return set_error(serror, SCRIPT_ERR_SIG_DER);
0167     }
0168     unsigned int nLenR = vchSig[3];
0169     unsigned int nLenS = vchSig[5+nLenR];
0170     const unsigned char *S = &vchSig[6+nLenR];
0171     // If the S value is above the order of the curve divided by two, its
0172     // complement modulo the order could have been used instead, which is
0173     // one byte shorter when encoded correctly.
0174     if (!eccrypto::CheckSignatureElement(S, nLenS, true))
0175         return set_error(serror, SCRIPT_ERR_SIG_HIGH_S);
0176 
0177     return true;
0178 }
0179 
0180 bool static IsDefinedHashtypeSignature(const valtype &vchSig) {
0181     if (vchSig.size() == 0) {
0182         return false;
0183     }
0184     unsigned char nHashType = vchSig[vchSig.size() - 1] & (~(SIGHASH_ANYONECANPAY));
0185     if (nHashType < SIGHASH_ALL || nHashType > SIGHASH_SINGLE)
0186         return false;
0187 
0188     return true;
0189 }
0190 
0191 bool static CheckSignatureEncoding(const valtype &vchSig, unsigned int flags, ScriptError* serror) {
0192     // Empty signature. Not strictly DER encoded, but allowed to provide a
0193     // compact way to provide an invalid signature for use with CHECK(MULTI)SIG
0194     if (vchSig.size() == 0) {
0195         return true;
0196     }
0197     if ((flags & (SCRIPT_VERIFY_DERSIG | SCRIPT_VERIFY_LOW_S | SCRIPT_VERIFY_STRICTENC)) != 0 && !IsValidSignatureEncoding(vchSig)) {
0198         return set_error(serror, SCRIPT_ERR_SIG_DER);
0199     } else if ((flags & SCRIPT_VERIFY_LOW_S) != 0 && !IsLowDERSignature(vchSig, serror)) {
0200         // serror is set
0201         return false;
0202     } else if ((flags & SCRIPT_VERIFY_STRICTENC) != 0 && !IsDefinedHashtypeSignature(vchSig)) {
0203         return set_error(serror, SCRIPT_ERR_SIG_HASHTYPE);
0204     }
0205     return true;
0206 }
0207 
0208 bool static CheckPubKeyEncoding(const valtype &vchSig, unsigned int flags, ScriptError* serror) {
0209     if ((flags & SCRIPT_VERIFY_STRICTENC) != 0 && !IsCompressedOrUncompressedPubKey(vchSig)) {
0210         return set_error(serror, SCRIPT_ERR_PUBKEYTYPE);
0211     }
0212     return true;
0213 }
0214 
0215 bool static CheckMinimalPush(const valtype& data, opcodetype opcode) {
0216     if (data.size() == 0) {
0217         // Could have used OP_0.
0218         return opcode == OP_0;
0219     } else if (data.size() == 1 && data[0] >= 1 && data[0] <= 16) {
0220         // Could have used OP_1 .. OP_16.
0221         return opcode == OP_1 + (data[0] - 1);
0222     } else if (data.size() == 1 && data[0] == 0x81) {
0223         // Could have used OP_1NEGATE.
0224         return opcode == OP_1NEGATE;
0225     } else if (data.size() <= 75) {
0226         // Could have used a direct push (opcode indicating number of bytes pushed + those bytes).
0227         return opcode == data.size();
0228     } else if (data.size() <= 255) {
0229         // Could have used OP_PUSHDATA.
0230         return opcode == OP_PUSHDATA1;
0231     } else if (data.size() <= 65535) {
0232         // Could have used OP_PUSHDATA2.
0233         return opcode == OP_PUSHDATA2;
0234     }
0235     return true;
0236 }
0237 
0238 bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
0239 {
0240     static const CScriptNum bnZero(0);
0241     static const CScriptNum bnOne(1);
0242     static const CScriptNum bnFalse(0);
0243     static const CScriptNum bnTrue(1);
0244     static const valtype vchFalse(0);
0245     static const valtype vchZero(0);
0246     static const valtype vchTrue(1, 1);
0247 
0248     CScript::const_iterator pc = script.begin();
0249     CScript::const_iterator pend = script.end();
0250     CScript::const_iterator pbegincodehash = script.begin();
0251     opcodetype opcode;
0252     valtype vchPushValue;
0253     vector<bool> vfExec;
0254     vector<valtype> altstack;
0255     set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR);
0256     if (script.size() > 10000)
0257         return set_error(serror, SCRIPT_ERR_SCRIPT_SIZE);
0258     int nOpCount = 0;
0259     bool fRequireMinimal = (flags & SCRIPT_VERIFY_MINIMALDATA) != 0;
0260 
0261     try
0262     {
0263         while (pc < pend)
0264         {
0265             bool fExec = !count(vfExec.begin(), vfExec.end(), false);
0266 
0267             //
0268             // Read instruction
0269             //
0270             if (!script.GetOp(pc, opcode, vchPushValue))
0271                 return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
0272             if (vchPushValue.size() > MAX_SCRIPT_ELEMENT_SIZE)
0273                 return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
0274 
0275             // Note how OP_RESERVED does not count towards the opcode limit.
0276             if (opcode > OP_16 && ++nOpCount > 201)
0277                 return set_error(serror, SCRIPT_ERR_OP_COUNT);
0278 
0279             if (opcode == OP_CAT ||
0280                 opcode == OP_SUBSTR ||
0281                 opcode == OP_LEFT ||
0282                 opcode == OP_RIGHT ||
0283                 opcode == OP_INVERT ||
0284                 opcode == OP_AND ||
0285                 opcode == OP_OR ||
0286                 opcode == OP_XOR ||
0287                 opcode == OP_2MUL ||
0288                 opcode == OP_2DIV ||
0289                 opcode == OP_MUL ||
0290                 opcode == OP_DIV ||
0291                 opcode == OP_MOD ||
0292                 opcode == OP_LSHIFT ||
0293                 opcode == OP_RSHIFT)
0294                 return set_error(serror, SCRIPT_ERR_DISABLED_OPCODE); // Disabled opcodes.
0295 
0296             if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4) {
0297                 if (fRequireMinimal && !CheckMinimalPush(vchPushValue, opcode)) {
0298                     return set_error(serror, SCRIPT_ERR_MINIMALDATA);
0299                 }
0300                 stack.push_back(vchPushValue);
0301             } else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
0302             switch (opcode)
0303             {
0304                 //
0305                 // Push value
0306                 //
0307                 case OP_1NEGATE:
0308                 case OP_1:
0309                 case OP_2:
0310                 case OP_3:
0311                 case OP_4:
0312                 case OP_5:
0313                 case OP_6:
0314                 case OP_7:
0315                 case OP_8:
0316                 case OP_9:
0317                 case OP_10:
0318                 case OP_11:
0319                 case OP_12:
0320                 case OP_13:
0321                 case OP_14:
0322                 case OP_15:
0323                 case OP_16:
0324                 {
0325                     // ( -- value)
0326                     CScriptNum bn((int)opcode - (int)(OP_1 - 1));
0327                     stack.push_back(bn.getvch());
0328                     // The result of these opcodes should always be the minimal way to push the data
0329                     // they push, so no need for a CheckMinimalPush here.
0330                 }
0331                 break;
0332 
0333 
0334                 //
0335                 // Control
0336                 //
0337                 case OP_NOP:
0338                 break;
0339 
0340                 case OP_NOP1: case OP_NOP2: case OP_NOP3: case OP_NOP4: case OP_NOP5:
0341                 case OP_NOP6: case OP_NOP7: case OP_NOP8: case OP_NOP9: case OP_NOP10:
0342                 {
0343                     if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS)
0344                         return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS);
0345                 }
0346                 break;
0347 
0348                 case OP_IF:
0349                 case OP_NOTIF:
0350                 {
0351                     // <expression> if [statements] [else [statements]] endif
0352                     bool fValue = false;
0353                     if (fExec)
0354                     {
0355                         if (stack.size() < 1)
0356                             return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
0357                         valtype& vch = stacktop(-1);
0358                         fValue = CastToBool(vch);
0359                         if (opcode == OP_NOTIF)
0360                             fValue = !fValue;
0361                         popstack(stack);
0362                     }
0363                     vfExec.push_back(fValue);
0364                 }
0365                 break;
0366 
0367                 case OP_ELSE:
0368                 {
0369                     if (vfExec.empty())
0370                         return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
0371                     vfExec.back() = !vfExec.back();
0372                 }
0373                 break;
0374 
0375                 case OP_ENDIF:
0376                 {
0377                     if (vfExec.empty())
0378                         return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
0379                     vfExec.pop_back();
0380                 }
0381                 break;
0382 
0383                 case OP_VERIFY:
0384                 {
0385                     // (true -- ) or
0386                     // (false -- false) and return
0387                     if (stack.size() < 1)
0388                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0389                     bool fValue = CastToBool(stacktop(-1));
0390                     if (fValue)
0391                         popstack(stack);
0392                     else
0393                         return set_error(serror, SCRIPT_ERR_VERIFY);
0394                 }
0395                 break;
0396 
0397                 case OP_RETURN:
0398                 {
0399                     return set_error(serror, SCRIPT_ERR_OP_RETURN);
0400                 }
0401                 break;
0402 
0403 
0404                 //
0405                 // Stack ops
0406                 //
0407                 case OP_TOALTSTACK:
0408                 {
0409                     if (stack.size() < 1)
0410                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0411                     altstack.push_back(stacktop(-1));
0412                     popstack(stack);
0413                 }
0414                 break;
0415 
0416                 case OP_FROMALTSTACK:
0417                 {
0418                     if (altstack.size() < 1)
0419                         return set_error(serror, SCRIPT_ERR_INVALID_ALTSTACK_OPERATION);
0420                     stack.push_back(altstacktop(-1));
0421                     popstack(altstack);
0422                 }
0423                 break;
0424 
0425                 case OP_2DROP:
0426                 {
0427                     // (x1 x2 -- )
0428                     if (stack.size() < 2)
0429                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0430                     popstack(stack);
0431                     popstack(stack);
0432                 }
0433                 break;
0434 
0435                 case OP_2DUP:
0436                 {
0437                     // (x1 x2 -- x1 x2 x1 x2)
0438                     if (stack.size() < 2)
0439                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0440                     valtype vch1 = stacktop(-2);
0441                     valtype vch2 = stacktop(-1);
0442                     stack.push_back(vch1);
0443                     stack.push_back(vch2);
0444                 }
0445                 break;
0446 
0447                 case OP_3DUP:
0448                 {
0449                     // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)
0450                     if (stack.size() < 3)
0451                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0452                     valtype vch1 = stacktop(-3);
0453                     valtype vch2 = stacktop(-2);
0454                     valtype vch3 = stacktop(-1);
0455                     stack.push_back(vch1);
0456                     stack.push_back(vch2);
0457                     stack.push_back(vch3);
0458                 }
0459                 break;
0460 
0461                 case OP_2OVER:
0462                 {
0463                     // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
0464                     if (stack.size() < 4)
0465                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0466                     valtype vch1 = stacktop(-4);
0467                     valtype vch2 = stacktop(-3);
0468                     stack.push_back(vch1);
0469                     stack.push_back(vch2);
0470                 }
0471                 break;
0472 
0473                 case OP_2ROT:
0474                 {
0475                     // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
0476                     if (stack.size() < 6)
0477                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0478                     valtype vch1 = stacktop(-6);
0479                     valtype vch2 = stacktop(-5);
0480                     stack.erase(stack.end()-6, stack.end()-4);
0481                     stack.push_back(vch1);
0482                     stack.push_back(vch2);
0483                 }
0484                 break;
0485 
0486                 case OP_2SWAP:
0487                 {
0488                     // (x1 x2 x3 x4 -- x3 x4 x1 x2)
0489                     if (stack.size() < 4)
0490                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0491                     swap(stacktop(-4), stacktop(-2));
0492                     swap(stacktop(-3), stacktop(-1));
0493                 }
0494                 break;
0495 
0496                 case OP_IFDUP:
0497                 {
0498                     // (x - 0 | x x)
0499                     if (stack.size() < 1)
0500                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0501                     valtype vch = stacktop(-1);
0502                     if (CastToBool(vch))
0503                         stack.push_back(vch);
0504                 }
0505                 break;
0506 
0507                 case OP_DEPTH:
0508                 {
0509                     // -- stacksize
0510                     CScriptNum bn(stack.size());
0511                     stack.push_back(bn.getvch());
0512                 }
0513                 break;
0514 
0515                 case OP_DROP:
0516                 {
0517                     // (x -- )
0518                     if (stack.size() < 1)
0519                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0520                     popstack(stack);
0521                 }
0522                 break;
0523 
0524                 case OP_DUP:
0525                 {
0526                     // (x -- x x)
0527                     if (stack.size() < 1)
0528                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0529                     valtype vch = stacktop(-1);
0530                     stack.push_back(vch);
0531                 }
0532                 break;
0533 
0534                 case OP_NIP:
0535                 {
0536                     // (x1 x2 -- x2)
0537                     if (stack.size() < 2)
0538                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0539                     stack.erase(stack.end() - 2);
0540                 }
0541                 break;
0542 
0543                 case OP_OVER:
0544                 {
0545                     // (x1 x2 -- x1 x2 x1)
0546                     if (stack.size() < 2)
0547                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0548                     valtype vch = stacktop(-2);
0549                     stack.push_back(vch);
0550                 }
0551                 break;
0552 
0553                 case OP_PICK:
0554                 case OP_ROLL:
0555                 {
0556                     // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
0557                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
0558                     if (stack.size() < 2)
0559                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0560                     int n = CScriptNum(stacktop(-1), fRequireMinimal).getint();
0561                     popstack(stack);
0562                     if (n < 0 || n >= (int)stack.size())
0563                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0564                     valtype vch = stacktop(-n-1);
0565                     if (opcode == OP_ROLL)
0566                         stack.erase(stack.end()-n-1);
0567                     stack.push_back(vch);
0568                 }
0569                 break;
0570 
0571                 case OP_ROT:
0572                 {
0573                     // (x1 x2 x3 -- x2 x3 x1)
0574                     //  x2 x1 x3  after first swap
0575                     //  x2 x3 x1  after second swap
0576                     if (stack.size() < 3)
0577                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0578                     swap(stacktop(-3), stacktop(-2));
0579                     swap(stacktop(-2), stacktop(-1));
0580                 }
0581                 break;
0582 
0583                 case OP_SWAP:
0584                 {
0585                     // (x1 x2 -- x2 x1)
0586                     if (stack.size() < 2)
0587                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0588                     swap(stacktop(-2), stacktop(-1));
0589                 }
0590                 break;
0591 
0592                 case OP_TUCK:
0593                 {
0594                     // (x1 x2 -- x2 x1 x2)
0595                     if (stack.size() < 2)
0596                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0597                     valtype vch = stacktop(-1);
0598                     stack.insert(stack.end()-2, vch);
0599                 }
0600                 break;
0601 
0602 
0603                 case OP_SIZE:
0604                 {
0605                     // (in -- in size)
0606                     if (stack.size() < 1)
0607                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0608                     CScriptNum bn(stacktop(-1).size());
0609                     stack.push_back(bn.getvch());
0610                 }
0611                 break;
0612 
0613 
0614                 //
0615                 // Bitwise logic
0616                 //
0617                 case OP_EQUAL:
0618                 case OP_EQUALVERIFY:
0619                 //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
0620                 {
0621                     // (x1 x2 - bool)
0622                     if (stack.size() < 2)
0623                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0624                     valtype& vch1 = stacktop(-2);
0625                     valtype& vch2 = stacktop(-1);
0626                     bool fEqual = (vch1 == vch2);
0627                     // OP_NOTEQUAL is disabled because it would be too easy to say
0628                     // something like n != 1 and have some wiseguy pass in 1 with extra
0629                     // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
0630                     //if (opcode == OP_NOTEQUAL)
0631                     //    fEqual = !fEqual;
0632                     popstack(stack);
0633                     popstack(stack);
0634                     stack.push_back(fEqual ? vchTrue : vchFalse);
0635                     if (opcode == OP_EQUALVERIFY)
0636                     {
0637                         if (fEqual)
0638                             popstack(stack);
0639                         else
0640                             return set_error(serror, SCRIPT_ERR_EQUALVERIFY);
0641                     }
0642                 }
0643                 break;
0644 
0645 
0646                 //
0647                 // Numeric
0648                 //
0649                 case OP_1ADD:
0650                 case OP_1SUB:
0651                 case OP_NEGATE:
0652                 case OP_ABS:
0653                 case OP_NOT:
0654                 case OP_0NOTEQUAL:
0655                 {
0656                     // (in -- out)
0657                     if (stack.size() < 1)
0658                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0659                     CScriptNum bn(stacktop(-1), fRequireMinimal);
0660                     switch (opcode)
0661                     {
0662                     case OP_1ADD:       bn += bnOne; break;
0663                     case OP_1SUB:       bn -= bnOne; break;
0664                     case OP_NEGATE:     bn = -bn; break;
0665                     case OP_ABS:        if (bn < bnZero) bn = -bn; break;
0666                     case OP_NOT:        bn = (bn == bnZero); break;
0667                     case OP_0NOTEQUAL:  bn = (bn != bnZero); break;
0668                     default:            assert(!"invalid opcode"); break;
0669                     }
0670                     popstack(stack);
0671                     stack.push_back(bn.getvch());
0672                 }
0673                 break;
0674 
0675                 case OP_ADD:
0676                 case OP_SUB:
0677                 case OP_BOOLAND:
0678                 case OP_BOOLOR:
0679                 case OP_NUMEQUAL:
0680                 case OP_NUMEQUALVERIFY:
0681                 case OP_NUMNOTEQUAL:
0682                 case OP_LESSTHAN:
0683                 case OP_GREATERTHAN:
0684                 case OP_LESSTHANOREQUAL:
0685                 case OP_GREATERTHANOREQUAL:
0686                 case OP_MIN:
0687                 case OP_MAX:
0688                 {
0689                     // (x1 x2 -- out)
0690                     if (stack.size() < 2)
0691                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0692                     CScriptNum bn1(stacktop(-2), fRequireMinimal);
0693                     CScriptNum bn2(stacktop(-1), fRequireMinimal);
0694                     CScriptNum bn(0);
0695                     switch (opcode)
0696                     {
0697                     case OP_ADD:
0698                         bn = bn1 + bn2;
0699                         break;
0700 
0701                     case OP_SUB:
0702                         bn = bn1 - bn2;
0703                         break;
0704 
0705                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;
0706                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;
0707                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;
0708                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;
0709                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;
0710                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;
0711                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;
0712                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;
0713                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;
0714                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;
0715                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;
0716                     default:                     assert(!"invalid opcode"); break;
0717                     }
0718                     popstack(stack);
0719                     popstack(stack);
0720                     stack.push_back(bn.getvch());
0721 
0722                     if (opcode == OP_NUMEQUALVERIFY)
0723                     {
0724                         if (CastToBool(stacktop(-1)))
0725                             popstack(stack);
0726                         else
0727                             return set_error(serror, SCRIPT_ERR_NUMEQUALVERIFY);
0728                     }
0729                 }
0730                 break;
0731 
0732                 case OP_WITHIN:
0733                 {
0734                     // (x min max -- out)
0735                     if (stack.size() < 3)
0736                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0737                     CScriptNum bn1(stacktop(-3), fRequireMinimal);
0738                     CScriptNum bn2(stacktop(-2), fRequireMinimal);
0739                     CScriptNum bn3(stacktop(-1), fRequireMinimal);
0740                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
0741                     popstack(stack);
0742                     popstack(stack);
0743                     popstack(stack);
0744                     stack.push_back(fValue ? vchTrue : vchFalse);
0745                 }
0746                 break;
0747 
0748 
0749                 //
0750                 // Crypto
0751                 //
0752                 case OP_RIPEMD160:
0753                 case OP_SHA1:
0754                 case OP_SHA256:
0755                 case OP_HASH160:
0756                 case OP_HASH256:
0757                 {
0758                     // (in -- hash)
0759                     if (stack.size() < 1)
0760                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0761                     valtype& vch = stacktop(-1);
0762                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);
0763                     if (opcode == OP_RIPEMD160)
0764                         CRIPEMD160().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash));
0765                     else if (opcode == OP_SHA1)
0766                         CSHA1().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash));
0767                     else if (opcode == OP_SHA256)
0768                         CSHA256().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash));
0769                     else if (opcode == OP_HASH160)
0770                         CHash160().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash));
0771                     else if (opcode == OP_HASH256)
0772                         CHash256().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash));
0773                     popstack(stack);
0774                     stack.push_back(vchHash);
0775                 }
0776                 break;                                   
0777 
0778                 case OP_CODESEPARATOR:
0779                 {
0780                     // Hash starts after the code separator
0781                     pbegincodehash = pc;
0782                 }
0783                 break;
0784 
0785                 case OP_CHECKSIG:
0786                 case OP_CHECKSIGVERIFY:
0787                 {
0788                     // (sig pubkey -- bool)
0789                     if (stack.size() < 2)
0790                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0791 
0792                     valtype& vchSig    = stacktop(-2);
0793                     valtype& vchPubKey = stacktop(-1);
0794 
0795                     // Subset of script starting at the most recent codeseparator
0796                     CScript scriptCode(pbegincodehash, pend);
0797 
0798                     // Drop the signature, since there's no way for a signature to sign itself
0799                     scriptCode.FindAndDelete(CScript(vchSig));
0800 
0801                     if (!CheckSignatureEncoding(vchSig, flags, serror) || !CheckPubKeyEncoding(vchPubKey, flags, serror)) {
0802                         //serror is set
0803                         return false;
0804                     }
0805                     bool fSuccess = checker.CheckSig(vchSig, vchPubKey, scriptCode);
0806 
0807                     popstack(stack);
0808                     popstack(stack);
0809                     stack.push_back(fSuccess ? vchTrue : vchFalse);
0810                     if (opcode == OP_CHECKSIGVERIFY)
0811                     {
0812                         if (fSuccess)
0813                             popstack(stack);
0814                         else
0815                             return set_error(serror, SCRIPT_ERR_CHECKSIGVERIFY);
0816                     }
0817                 }
0818                 break;
0819 
0820                 case OP_CHECKMULTISIG:
0821                 case OP_CHECKMULTISIGVERIFY:
0822                 {
0823                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
0824 
0825                     int i = 1;
0826                     if ((int)stack.size() < i)
0827                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0828 
0829                     int nKeysCount = CScriptNum(stacktop(-i), fRequireMinimal).getint();
0830                     if (nKeysCount < 0 || nKeysCount > 20)
0831                         return set_error(serror, SCRIPT_ERR_PUBKEY_COUNT);
0832                     nOpCount += nKeysCount;
0833                     if (nOpCount > 201)
0834                         return set_error(serror, SCRIPT_ERR_OP_COUNT);
0835                     int ikey = ++i;
0836                     i += nKeysCount;
0837                     if ((int)stack.size() < i)
0838                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0839 
0840                     int nSigsCount = CScriptNum(stacktop(-i), fRequireMinimal).getint();
0841                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
0842                         return set_error(serror, SCRIPT_ERR_SIG_COUNT);
0843                     int isig = ++i;
0844                     i += nSigsCount;
0845                     if ((int)stack.size() < i)
0846                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0847 
0848                     // Subset of script starting at the most recent codeseparator
0849                     CScript scriptCode(pbegincodehash, pend);
0850 
0851                     // Drop the signatures, since there's no way for a signature to sign itself
0852                     for (int k = 0; k < nSigsCount; k++)
0853                     {
0854                         valtype& vchSig = stacktop(-isig-k);
0855                         scriptCode.FindAndDelete(CScript(vchSig));
0856                     }
0857 
0858                     bool fSuccess = true;
0859                     while (fSuccess && nSigsCount > 0)
0860                     {
0861                         valtype& vchSig    = stacktop(-isig);
0862                         valtype& vchPubKey = stacktop(-ikey);
0863 
0864                         // Note how this makes the exact order of pubkey/signature evaluation
0865                         // distinguishable by CHECKMULTISIG NOT if the STRICTENC flag is set.
0866                         // See the script_(in)valid tests for details.
0867                         if (!CheckSignatureEncoding(vchSig, flags, serror) || !CheckPubKeyEncoding(vchPubKey, flags, serror)) {
0868                             // serror is set
0869                             return false;
0870                         }
0871 
0872                         // Check signature
0873                         bool fOk = checker.CheckSig(vchSig, vchPubKey, scriptCode);
0874 
0875                         if (fOk) {
0876                             isig++;
0877                             nSigsCount--;
0878                         }
0879                         ikey++;
0880                         nKeysCount--;
0881 
0882                         // If there are more signatures left than keys left,
0883                         // then too many signatures have failed. Exit early,
0884                         // without checking any further signatures.
0885                         if (nSigsCount > nKeysCount)
0886                             fSuccess = false;
0887                     }
0888 
0889                     // Clean up stack of actual arguments
0890                     while (i-- > 1)
0891                         popstack(stack);
0892 
0893                     // A bug causes CHECKMULTISIG to consume one extra argument
0894                     // whose contents were not checked in any way.
0895                     //
0896                     // Unfortunately this is a potential source of mutability,
0897                     // so optionally verify it is exactly equal to zero prior
0898                     // to removing it from the stack.
0899                     if (stack.size() < 1)
0900                         return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0901                     if ((flags & SCRIPT_VERIFY_NULLDUMMY) && stacktop(-1).size())
0902                         return set_error(serror, SCRIPT_ERR_SIG_NULLDUMMY);
0903                     popstack(stack);
0904 
0905                     stack.push_back(fSuccess ? vchTrue : vchFalse);
0906 
0907                     if (opcode == OP_CHECKMULTISIGVERIFY)
0908                     {
0909                         if (fSuccess)
0910                             popstack(stack);
0911                         else
0912                             return set_error(serror, SCRIPT_ERR_CHECKMULTISIGVERIFY);
0913                     }
0914                 }
0915                 break;
0916 
0917                 default:
0918                     return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
0919             }
0920 
0921             // Size limits
0922             if (stack.size() + altstack.size() > 1000)
0923                 return set_error(serror, SCRIPT_ERR_STACK_SIZE);
0924         }
0925     }
0926     catch (...)
0927     {
0928         return set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR);
0929     }
0930 
0931     if (!vfExec.empty())
0932         return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
0933 
0934     return set_success(serror);
0935 }
0936 
0937 namespace {
0938 
0939 /**
0940  * Wrapper that serializes like CTransaction, but with the modifications
0941  *  required for the signature hash done in-place
0942  */
0943 class CTransactionSignatureSerializer {
0944 private:
0945     const CTransaction &txTo;  //! reference to the spending transaction (the one being serialized)
0946     const CScript &scriptCode; //! output script being consumed
0947     const unsigned int nIn;    //! input index of txTo being signed
0948     const bool fAnyoneCanPay;  //! whether the hashtype has the SIGHASH_ANYONECANPAY flag set
0949     const bool fHashSingle;    //! whether the hashtype is SIGHASH_SINGLE
0950     const bool fHashNone;      //! whether the hashtype is SIGHASH_NONE
0951 
0952 public:
0953     CTransactionSignatureSerializer(const CTransaction &txToIn, const CScript &scriptCodeIn, unsigned int nInIn, int nHashTypeIn) :
0954         txTo(txToIn), scriptCode(scriptCodeIn), nIn(nInIn),
0955         fAnyoneCanPay(!!(nHashTypeIn & SIGHASH_ANYONECANPAY)),
0956         fHashSingle((nHashTypeIn & 0x1f) == SIGHASH_SINGLE),
0957         fHashNone((nHashTypeIn & 0x1f) == SIGHASH_NONE) {}
0958 
0959     /** Serialize the passed scriptCode, skipping OP_CODESEPARATORs */
0960     template<typename S>
0961     void SerializeScriptCode(S &s, int nType, int nVersion) const {
0962         CScript::const_iterator it = scriptCode.begin();
0963         CScript::const_iterator itBegin = it;
0964         opcodetype opcode;
0965         unsigned int nCodeSeparators = 0;
0966         while (scriptCode.GetOp(it, opcode)) {
0967             if (opcode == OP_CODESEPARATOR)
0968                 nCodeSeparators++;
0969         }
0970         ::WriteCompactSize(s, scriptCode.size() - nCodeSeparators);
0971         it = itBegin;
0972         while (scriptCode.GetOp(it, opcode)) {
0973             if (opcode == OP_CODESEPARATOR) {
0974                 s.write((char*)&itBegin[0], it-itBegin-1);
0975                 itBegin = it;
0976             }
0977         }
0978         if (itBegin != scriptCode.end())
0979             s.write((char*)&itBegin[0], it-itBegin);
0980     }
0981 
0982     /** Serialize an input of txTo */
0983     template<typename S>
0984     void SerializeInput(S &s, unsigned int nInput, int nType, int nVersion) const {
0985         // In case of SIGHASH_ANYONECANPAY, only the input being signed is serialized
0986         if (fAnyoneCanPay)
0987             nInput = nIn;
0988         // Serialize the prevout
0989         ::Serialize(s, txTo.vin[nInput].prevout, nType, nVersion);
0990         // Serialize the script
0991         if (nInput != nIn)
0992             // Blank out other inputs' signatures
0993             ::Serialize(s, CScript(), nType, nVersion);
0994         else
0995             SerializeScriptCode(s, nType, nVersion);
0996         // Serialize the nSequence
0997         if (nInput != nIn && (fHashSingle || fHashNone))
0998             // let the others update at will
0999             ::Serialize(s, (int)0, nType, nVersion);
1000         else
1001             ::Serialize(s, txTo.vin[nInput].nSequence, nType, nVersion);
1002     }
1003 
1004     /** Serialize an output of txTo */
1005     template<typename S>
1006     void SerializeOutput(S &s, unsigned int nOutput, int nType, int nVersion) const {
1007         if (fHashSingle && nOutput != nIn)
1008             // Do not lock-in the txout payee at other indices as txin
1009             ::Serialize(s, CTxOut(), nType, nVersion);
1010         else
1011             ::Serialize(s, txTo.vout[nOutput], nType, nVersion);
1012     }
1013 
1014     /** Serialize txTo */
1015     template<typename S>
1016     void Serialize(S &s, int nType, int nVersion) const {
1017         // Serialize nVersion
1018         ::Serialize(s, txTo.nVersion, nType, nVersion);
1019         // Serialize vin
1020         unsigned int nInputs = fAnyoneCanPay ? 1 : txTo.vin.size();
1021         ::WriteCompactSize(s, nInputs);
1022         for (unsigned int nInput = 0; nInput < nInputs; nInput++)
1023              SerializeInput(s, nInput, nType, nVersion);
1024         // Serialize vout
1025         unsigned int nOutputs = fHashNone ? 0 : (fHashSingle ? nIn+1 : txTo.vout.size());
1026         ::WriteCompactSize(s, nOutputs);
1027         for (unsigned int nOutput = 0; nOutput < nOutputs; nOutput++)
1028              SerializeOutput(s, nOutput, nType, nVersion);
1029         // Serialize nLockTime
1030         ::Serialize(s, txTo.nLockTime, nType, nVersion);
1031     }
1032 };
1033 
1034 } // anon namespace
1035 
1036 uint256 SignatureHash(const CScript& scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
1037 {
1038     if (nIn >= txTo.vin.size()) {
1039         //  nIn out of range
1040         return 1;
1041     }
1042 
1043     // Check for invalid use of SIGHASH_SINGLE
1044     if ((nHashType & 0x1f) == SIGHASH_SINGLE) {
1045         if (nIn >= txTo.vout.size()) {
1046             //  nOut out of range
1047             return 1;
1048         }
1049     }
1050 
1051     // Wrapper to serialize only the necessary parts of the transaction being signed
1052     CTransactionSignatureSerializer txTmp(txTo, scriptCode, nIn, nHashType);
1053 
1054     // Serialize and hash
1055     CHashWriter ss(SER_GETHASH, 0);
1056     ss << txTmp << nHashType;
1057     return ss.GetHash();
1058 }
1059 
1060 bool TransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const
1061 {
1062     return pubkey.Verify(sighash, vchSig);
1063 }
1064 
1065 bool TransactionSignatureChecker::CheckSig(const vector<unsigned char>& vchSigIn, const vector<unsigned char>& vchPubKey, const CScript& scriptCode) const
1066 {
1067     CPubKey pubkey(vchPubKey);
1068     if (!pubkey.IsValid())
1069         return false;
1070 
1071     // Hash type is one byte tacked on to the end of the signature
1072     vector<unsigned char> vchSig(vchSigIn);
1073     if (vchSig.empty())
1074         return false;
1075     int nHashType = vchSig.back();
1076     vchSig.pop_back();
1077 
1078     uint256 sighash = SignatureHash(scriptCode, *txTo, nIn, nHashType);
1079 
1080     if (!VerifySignature(vchSig, pubkey, sighash))
1081         return false;
1082 
1083     return true;
1084 }
1085 
1086 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
1087 {
1088     set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR);
1089 
1090     if ((flags & SCRIPT_VERIFY_SIGPUSHONLY) != 0 && !scriptSig.IsPushOnly()) {
1091         return set_error(serror, SCRIPT_ERR_SIG_PUSHONLY);
1092     }
1093 
1094     vector<vector<unsigned char> > stack, stackCopy;
1095     if (!EvalScript(stack, scriptSig, flags, checker, serror))
1096         // serror is set
1097         return false;
1098     if (flags & SCRIPT_VERIFY_P2SH)
1099         stackCopy = stack;
1100     if (!EvalScript(stack, scriptPubKey, flags, checker, serror))
1101         // serror is set
1102         return false;
1103     if (stack.empty())
1104         return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1105 
1106     if (CastToBool(stack.back()) == false)
1107         return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1108 
1109     // Additional validation for spend-to-script-hash transactions:
1110     if ((flags & SCRIPT_VERIFY_P2SH) && scriptPubKey.IsPayToScriptHash())
1111     {
1112         // scriptSig must be literals-only or validation fails
1113         if (!scriptSig.IsPushOnly())
1114             return set_error(serror, SCRIPT_ERR_SIG_PUSHONLY);
1115 
1116         // stackCopy cannot be empty here, because if it was the
1117         // P2SH  HASH <> EQUAL  scriptPubKey would be evaluated with
1118         // an empty stack and the EvalScript above would return false.
1119         assert(!stackCopy.empty());
1120 
1121         const valtype& pubKeySerialized = stackCopy.back();
1122         CScript pubKey2(pubKeySerialized.begin(), pubKeySerialized.end());
1123         popstack(stackCopy);
1124 
1125         if (!EvalScript(stackCopy, pubKey2, flags, checker, serror))
1126             // serror is set
1127             return false;
1128         if (stackCopy.empty())
1129             return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1130         if (!CastToBool(stackCopy.back()))
1131             return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1132         else
1133             return set_success(serror);
1134     }
1135 
1136     return set_success(serror);
1137 }