Back to home page

Bitcoin sources

 
 

    


0001 // Copyright (c) 2009-2010 Satoshi Nakamoto
0002 // Copyright (c) 2011 The Bitcoin developers
0003 // Distributed under the MIT/X11 software license, see the accompanying
0004 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
0005 #include "headers.h"
0006 
0007 using namespace std;
0008 using namespace boost;
0009 
0010 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType);
0011 
0012 
0013 
0014 typedef vector<unsigned char> valtype;
0015 static const valtype vchFalse(0);
0016 static const valtype vchZero(0);
0017 static const valtype vchTrue(1, 1);
0018 static const CBigNum bnZero(0);
0019 static const CBigNum bnOne(1);
0020 static const CBigNum bnFalse(0);
0021 static const CBigNum bnTrue(1);
0022 static const size_t nMaxNumSize = 4;
0023 
0024 
0025 CBigNum CastToBigNum(const valtype& vch)
0026 {
0027     if (vch.size() > nMaxNumSize)
0028         throw runtime_error("CastToBigNum() : overflow");
0029     // Get rid of extra leading zeros
0030     return CBigNum(CBigNum(vch).getvch());
0031 }
0032 
0033 bool CastToBool(const valtype& vch)
0034 {
0035     for (int i = 0; i < vch.size(); i++)
0036     {
0037         if (vch[i] != 0)
0038         {
0039             // Can be negative zero
0040             if (i == vch.size()-1 && vch[i] == 0x80)
0041                 return false;
0042             return true;
0043         }
0044     }
0045     return false;
0046 }
0047 
0048 void MakeSameSize(valtype& vch1, valtype& vch2)
0049 {
0050     // Lengthen the shorter one
0051     if (vch1.size() < vch2.size())
0052         vch1.resize(vch2.size(), 0);
0053     if (vch2.size() < vch1.size())
0054         vch2.resize(vch1.size(), 0);
0055 }
0056 
0057 
0058 
0059 //
0060 // Script is a stack machine (like Forth) that evaluates a predicate
0061 // returning a bool indicating valid or not.  There are no loops.
0062 //
0063 #define stacktop(i)  (stack.at(stack.size()+(i)))
0064 #define altstacktop(i)  (altstack.at(altstack.size()+(i)))
0065 static inline void popstack(vector<valtype>& stack)
0066 {
0067     if (stack.empty())
0068         throw runtime_error("popstack() : stack empty");
0069     stack.pop_back();
0070 }
0071 
0072 
0073 bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, int nHashType)
0074 {
0075     CAutoBN_CTX pctx;
0076     CScript::const_iterator pc = script.begin();
0077     CScript::const_iterator pend = script.end();
0078     CScript::const_iterator pbegincodehash = script.begin();
0079     opcodetype opcode;
0080     valtype vchPushValue;
0081     vector<bool> vfExec;
0082     vector<valtype> altstack;
0083     if (script.size() > 10000)
0084         return false;
0085     int nOpCount = 0;
0086 
0087 
0088     try
0089     {
0090         while (pc < pend)
0091         {
0092             bool fExec = !count(vfExec.begin(), vfExec.end(), false);
0093 
0094             //
0095             // Read instruction
0096             //
0097             if (!script.GetOp(pc, opcode, vchPushValue))
0098                 return false;
0099             if (vchPushValue.size() > 520)
0100                 return false;
0101             if (opcode > OP_16 && ++nOpCount > 201)
0102                 return false;
0103 
0104             if (opcode == OP_CAT ||
0105                 opcode == OP_SUBSTR ||
0106                 opcode == OP_LEFT ||
0107                 opcode == OP_RIGHT ||
0108                 opcode == OP_INVERT ||
0109                 opcode == OP_AND ||
0110                 opcode == OP_OR ||
0111                 opcode == OP_XOR ||
0112                 opcode == OP_2MUL ||
0113                 opcode == OP_2DIV ||
0114                 opcode == OP_MUL ||
0115                 opcode == OP_DIV ||
0116                 opcode == OP_MOD ||
0117                 opcode == OP_LSHIFT ||
0118                 opcode == OP_RSHIFT)
0119                 return false;
0120 
0121             if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4)
0122                 stack.push_back(vchPushValue);
0123             else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
0124             switch (opcode)
0125             {
0126                 //
0127                 // Push value
0128                 //
0129                 case OP_1NEGATE:
0130                 case OP_1:
0131                 case OP_2:
0132                 case OP_3:
0133                 case OP_4:
0134                 case OP_5:
0135                 case OP_6:
0136                 case OP_7:
0137                 case OP_8:
0138                 case OP_9:
0139                 case OP_10:
0140                 case OP_11:
0141                 case OP_12:
0142                 case OP_13:
0143                 case OP_14:
0144                 case OP_15:
0145                 case OP_16:
0146                 {
0147                     // ( -- value)
0148                     CBigNum bn((int)opcode - (int)(OP_1 - 1));
0149                     stack.push_back(bn.getvch());
0150                 }
0151                 break;
0152 
0153 
0154                 //
0155                 // Control
0156                 //
0157                 case OP_NOP:
0158                 case OP_NOP1: case OP_NOP2: case OP_NOP3: case OP_NOP4: case OP_NOP5:
0159                 case OP_NOP6: case OP_NOP7: case OP_NOP8: case OP_NOP9: case OP_NOP10:
0160                 break;
0161 
0162                 case OP_IF:
0163                 case OP_NOTIF:
0164                 {
0165                     // <expression> if [statements] [else [statements]] endif
0166                     bool fValue = false;
0167                     if (fExec)
0168                     {
0169                         if (stack.size() < 1)
0170                             return false;
0171                         valtype& vch = stacktop(-1);
0172                         fValue = CastToBool(vch);
0173                         if (opcode == OP_NOTIF)
0174                             fValue = !fValue;
0175                         popstack(stack);
0176                     }
0177                     vfExec.push_back(fValue);
0178                 }
0179                 break;
0180 
0181                 case OP_ELSE:
0182                 {
0183                     if (vfExec.empty())
0184                         return false;
0185                     vfExec.back() = !vfExec.back();
0186                 }
0187                 break;
0188 
0189                 case OP_ENDIF:
0190                 {
0191                     if (vfExec.empty())
0192                         return false;
0193                     vfExec.pop_back();
0194                 }
0195                 break;
0196 
0197                 case OP_VERIFY:
0198                 {
0199                     // (true -- ) or
0200                     // (false -- false) and return
0201                     if (stack.size() < 1)
0202                         return false;
0203                     bool fValue = CastToBool(stacktop(-1));
0204                     if (fValue)
0205                         popstack(stack);
0206                     else
0207                         return false;
0208                 }
0209                 break;
0210 
0211                 case OP_RETURN:
0212                 {
0213                     return false;
0214                 }
0215                 break;
0216 
0217 
0218                 //
0219                 // Stack ops
0220                 //
0221                 case OP_TOALTSTACK:
0222                 {
0223                     if (stack.size() < 1)
0224                         return false;
0225                     altstack.push_back(stacktop(-1));
0226                     popstack(stack);
0227                 }
0228                 break;
0229 
0230                 case OP_FROMALTSTACK:
0231                 {
0232                     if (altstack.size() < 1)
0233                         return false;
0234                     stack.push_back(altstacktop(-1));
0235                     popstack(altstack);
0236                 }
0237                 break;
0238 
0239                 case OP_2DROP:
0240                 {
0241                     // (x1 x2 -- )
0242                     if (stack.size() < 2)
0243                         return false;
0244                     popstack(stack);
0245                     popstack(stack);
0246                 }
0247                 break;
0248 
0249                 case OP_2DUP:
0250                 {
0251                     // (x1 x2 -- x1 x2 x1 x2)
0252                     if (stack.size() < 2)
0253                         return false;
0254                     valtype vch1 = stacktop(-2);
0255                     valtype vch2 = stacktop(-1);
0256                     stack.push_back(vch1);
0257                     stack.push_back(vch2);
0258                 }
0259                 break;
0260 
0261                 case OP_3DUP:
0262                 {
0263                     // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)
0264                     if (stack.size() < 3)
0265                         return false;
0266                     valtype vch1 = stacktop(-3);
0267                     valtype vch2 = stacktop(-2);
0268                     valtype vch3 = stacktop(-1);
0269                     stack.push_back(vch1);
0270                     stack.push_back(vch2);
0271                     stack.push_back(vch3);
0272                 }
0273                 break;
0274 
0275                 case OP_2OVER:
0276                 {
0277                     // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
0278                     if (stack.size() < 4)
0279                         return false;
0280                     valtype vch1 = stacktop(-4);
0281                     valtype vch2 = stacktop(-3);
0282                     stack.push_back(vch1);
0283                     stack.push_back(vch2);
0284                 }
0285                 break;
0286 
0287                 case OP_2ROT:
0288                 {
0289                     // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
0290                     if (stack.size() < 6)
0291                         return false;
0292                     valtype vch1 = stacktop(-6);
0293                     valtype vch2 = stacktop(-5);
0294                     stack.erase(stack.end()-6, stack.end()-4);
0295                     stack.push_back(vch1);
0296                     stack.push_back(vch2);
0297                 }
0298                 break;
0299 
0300                 case OP_2SWAP:
0301                 {
0302                     // (x1 x2 x3 x4 -- x3 x4 x1 x2)
0303                     if (stack.size() < 4)
0304                         return false;
0305                     swap(stacktop(-4), stacktop(-2));
0306                     swap(stacktop(-3), stacktop(-1));
0307                 }
0308                 break;
0309 
0310                 case OP_IFDUP:
0311                 {
0312                     // (x - 0 | x x)
0313                     if (stack.size() < 1)
0314                         return false;
0315                     valtype vch = stacktop(-1);
0316                     if (CastToBool(vch))
0317                         stack.push_back(vch);
0318                 }
0319                 break;
0320 
0321                 case OP_DEPTH:
0322                 {
0323                     // -- stacksize
0324                     CBigNum bn(stack.size());
0325                     stack.push_back(bn.getvch());
0326                 }
0327                 break;
0328 
0329                 case OP_DROP:
0330                 {
0331                     // (x -- )
0332                     if (stack.size() < 1)
0333                         return false;
0334                     popstack(stack);
0335                 }
0336                 break;
0337 
0338                 case OP_DUP:
0339                 {
0340                     // (x -- x x)
0341                     if (stack.size() < 1)
0342                         return false;
0343                     valtype vch = stacktop(-1);
0344                     stack.push_back(vch);
0345                 }
0346                 break;
0347 
0348                 case OP_NIP:
0349                 {
0350                     // (x1 x2 -- x2)
0351                     if (stack.size() < 2)
0352                         return false;
0353                     stack.erase(stack.end() - 2);
0354                 }
0355                 break;
0356 
0357                 case OP_OVER:
0358                 {
0359                     // (x1 x2 -- x1 x2 x1)
0360                     if (stack.size() < 2)
0361                         return false;
0362                     valtype vch = stacktop(-2);
0363                     stack.push_back(vch);
0364                 }
0365                 break;
0366 
0367                 case OP_PICK:
0368                 case OP_ROLL:
0369                 {
0370                     // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
0371                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
0372                     if (stack.size() < 2)
0373                         return false;
0374                     int n = CastToBigNum(stacktop(-1)).getint();
0375                     popstack(stack);
0376                     if (n < 0 || n >= stack.size())
0377                         return false;
0378                     valtype vch = stacktop(-n-1);
0379                     if (opcode == OP_ROLL)
0380                         stack.erase(stack.end()-n-1);
0381                     stack.push_back(vch);
0382                 }
0383                 break;
0384 
0385                 case OP_ROT:
0386                 {
0387                     // (x1 x2 x3 -- x2 x3 x1)
0388                     //  x2 x1 x3  after first swap
0389                     //  x2 x3 x1  after second swap
0390                     if (stack.size() < 3)
0391                         return false;
0392                     swap(stacktop(-3), stacktop(-2));
0393                     swap(stacktop(-2), stacktop(-1));
0394                 }
0395                 break;
0396 
0397                 case OP_SWAP:
0398                 {
0399                     // (x1 x2 -- x2 x1)
0400                     if (stack.size() < 2)
0401                         return false;
0402                     swap(stacktop(-2), stacktop(-1));
0403                 }
0404                 break;
0405 
0406                 case OP_TUCK:
0407                 {
0408                     // (x1 x2 -- x2 x1 x2)
0409                     if (stack.size() < 2)
0410                         return false;
0411                     valtype vch = stacktop(-1);
0412                     stack.insert(stack.end()-2, vch);
0413                 }
0414                 break;
0415 
0416 
0417                 //
0418                 // Splice ops
0419                 //
0420                 case OP_CAT:
0421                 {
0422                     // (x1 x2 -- out)
0423                     if (stack.size() < 2)
0424                         return false;
0425                     valtype& vch1 = stacktop(-2);
0426                     valtype& vch2 = stacktop(-1);
0427                     vch1.insert(vch1.end(), vch2.begin(), vch2.end());
0428                     popstack(stack);
0429                     if (stacktop(-1).size() > 520)
0430                         return false;
0431                 }
0432                 break;
0433 
0434                 case OP_SUBSTR:
0435                 {
0436                     // (in begin size -- out)
0437                     if (stack.size() < 3)
0438                         return false;
0439                     valtype& vch = stacktop(-3);
0440                     int nBegin = CastToBigNum(stacktop(-2)).getint();
0441                     int nEnd = nBegin + CastToBigNum(stacktop(-1)).getint();
0442                     if (nBegin < 0 || nEnd < nBegin)
0443                         return false;
0444                     if (nBegin > vch.size())
0445                         nBegin = vch.size();
0446                     if (nEnd > vch.size())
0447                         nEnd = vch.size();
0448                     vch.erase(vch.begin() + nEnd, vch.end());
0449                     vch.erase(vch.begin(), vch.begin() + nBegin);
0450                     popstack(stack);
0451                     popstack(stack);
0452                 }
0453                 break;
0454 
0455                 case OP_LEFT:
0456                 case OP_RIGHT:
0457                 {
0458                     // (in size -- out)
0459                     if (stack.size() < 2)
0460                         return false;
0461                     valtype& vch = stacktop(-2);
0462                     int nSize = CastToBigNum(stacktop(-1)).getint();
0463                     if (nSize < 0)
0464                         return false;
0465                     if (nSize > vch.size())
0466                         nSize = vch.size();
0467                     if (opcode == OP_LEFT)
0468                         vch.erase(vch.begin() + nSize, vch.end());
0469                     else
0470                         vch.erase(vch.begin(), vch.end() - nSize);
0471                     popstack(stack);
0472                 }
0473                 break;
0474 
0475                 case OP_SIZE:
0476                 {
0477                     // (in -- in size)
0478                     if (stack.size() < 1)
0479                         return false;
0480                     CBigNum bn(stacktop(-1).size());
0481                     stack.push_back(bn.getvch());
0482                 }
0483                 break;
0484 
0485 
0486                 //
0487                 // Bitwise logic
0488                 //
0489                 case OP_INVERT:
0490                 {
0491                     // (in - out)
0492                     if (stack.size() < 1)
0493                         return false;
0494                     valtype& vch = stacktop(-1);
0495                     for (int i = 0; i < vch.size(); i++)
0496                         vch[i] = ~vch[i];
0497                 }
0498                 break;
0499 
0500                 case OP_AND:
0501                 case OP_OR:
0502                 case OP_XOR:
0503                 {
0504                     // (x1 x2 - out)
0505                     if (stack.size() < 2)
0506                         return false;
0507                     valtype& vch1 = stacktop(-2);
0508                     valtype& vch2 = stacktop(-1);
0509                     MakeSameSize(vch1, vch2);
0510                     if (opcode == OP_AND)
0511                     {
0512                         for (int i = 0; i < vch1.size(); i++)
0513                             vch1[i] &= vch2[i];
0514                     }
0515                     else if (opcode == OP_OR)
0516                     {
0517                         for (int i = 0; i < vch1.size(); i++)
0518                             vch1[i] |= vch2[i];
0519                     }
0520                     else if (opcode == OP_XOR)
0521                     {
0522                         for (int i = 0; i < vch1.size(); i++)
0523                             vch1[i] ^= vch2[i];
0524                     }
0525                     popstack(stack);
0526                 }
0527                 break;
0528 
0529                 case OP_EQUAL:
0530                 case OP_EQUALVERIFY:
0531                 //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
0532                 {
0533                     // (x1 x2 - bool)
0534                     if (stack.size() < 2)
0535                         return false;
0536                     valtype& vch1 = stacktop(-2);
0537                     valtype& vch2 = stacktop(-1);
0538                     bool fEqual = (vch1 == vch2);
0539                     // OP_NOTEQUAL is disabled because it would be too easy to say
0540                     // something like n != 1 and have some wiseguy pass in 1 with extra
0541                     // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
0542                     //if (opcode == OP_NOTEQUAL)
0543                     //    fEqual = !fEqual;
0544                     popstack(stack);
0545                     popstack(stack);
0546                     stack.push_back(fEqual ? vchTrue : vchFalse);
0547                     if (opcode == OP_EQUALVERIFY)
0548                     {
0549                         if (fEqual)
0550                             popstack(stack);
0551                         else
0552                             return false;
0553                     }
0554                 }
0555                 break;
0556 
0557 
0558                 //
0559                 // Numeric
0560                 //
0561                 case OP_1ADD:
0562                 case OP_1SUB:
0563                 case OP_2MUL:
0564                 case OP_2DIV:
0565                 case OP_NEGATE:
0566                 case OP_ABS:
0567                 case OP_NOT:
0568                 case OP_0NOTEQUAL:
0569                 {
0570                     // (in -- out)
0571                     if (stack.size() < 1)
0572                         return false;
0573                     CBigNum bn = CastToBigNum(stacktop(-1));
0574                     switch (opcode)
0575                     {
0576                     case OP_1ADD:       bn += bnOne; break;
0577                     case OP_1SUB:       bn -= bnOne; break;
0578                     case OP_2MUL:       bn <<= 1; break;
0579                     case OP_2DIV:       bn >>= 1; break;
0580                     case OP_NEGATE:     bn = -bn; break;
0581                     case OP_ABS:        if (bn < bnZero) bn = -bn; break;
0582                     case OP_NOT:        bn = (bn == bnZero); break;
0583                     case OP_0NOTEQUAL:  bn = (bn != bnZero); break;
0584                     default:            assert(!"invalid opcode"); break;
0585                     }
0586                     popstack(stack);
0587                     stack.push_back(bn.getvch());
0588                 }
0589                 break;
0590 
0591                 case OP_ADD:
0592                 case OP_SUB:
0593                 case OP_MUL:
0594                 case OP_DIV:
0595                 case OP_MOD:
0596                 case OP_LSHIFT:
0597                 case OP_RSHIFT:
0598                 case OP_BOOLAND:
0599                 case OP_BOOLOR:
0600                 case OP_NUMEQUAL:
0601                 case OP_NUMEQUALVERIFY:
0602                 case OP_NUMNOTEQUAL:
0603                 case OP_LESSTHAN:
0604                 case OP_GREATERTHAN:
0605                 case OP_LESSTHANOREQUAL:
0606                 case OP_GREATERTHANOREQUAL:
0607                 case OP_MIN:
0608                 case OP_MAX:
0609                 {
0610                     // (x1 x2 -- out)
0611                     if (stack.size() < 2)
0612                         return false;
0613                     CBigNum bn1 = CastToBigNum(stacktop(-2));
0614                     CBigNum bn2 = CastToBigNum(stacktop(-1));
0615                     CBigNum bn;
0616                     switch (opcode)
0617                     {
0618                     case OP_ADD:
0619                         bn = bn1 + bn2;
0620                         break;
0621 
0622                     case OP_SUB:
0623                         bn = bn1 - bn2;
0624                         break;
0625 
0626                     case OP_MUL:
0627                         if (!BN_mul(&bn, &bn1, &bn2, pctx))
0628                             return false;
0629                         break;
0630 
0631                     case OP_DIV:
0632                         if (!BN_div(&bn, NULL, &bn1, &bn2, pctx))
0633                             return false;
0634                         break;
0635 
0636                     case OP_MOD:
0637                         if (!BN_mod(&bn, &bn1, &bn2, pctx))
0638                             return false;
0639                         break;
0640 
0641                     case OP_LSHIFT:
0642                         if (bn2 < bnZero || bn2 > CBigNum(2048))
0643                             return false;
0644                         bn = bn1 << bn2.getulong();
0645                         break;
0646 
0647                     case OP_RSHIFT:
0648                         if (bn2 < bnZero || bn2 > CBigNum(2048))
0649                             return false;
0650                         bn = bn1 >> bn2.getulong();
0651                         break;
0652 
0653                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;
0654                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;
0655                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;
0656                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;
0657                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;
0658                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;
0659                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;
0660                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;
0661                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;
0662                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;
0663                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;
0664                     default:                     assert(!"invalid opcode"); break;
0665                     }
0666                     popstack(stack);
0667                     popstack(stack);
0668                     stack.push_back(bn.getvch());
0669 
0670                     if (opcode == OP_NUMEQUALVERIFY)
0671                     {
0672                         if (CastToBool(stacktop(-1)))
0673                             popstack(stack);
0674                         else
0675                             return false;
0676                     }
0677                 }
0678                 break;
0679 
0680                 case OP_WITHIN:
0681                 {
0682                     // (x min max -- out)
0683                     if (stack.size() < 3)
0684                         return false;
0685                     CBigNum bn1 = CastToBigNum(stacktop(-3));
0686                     CBigNum bn2 = CastToBigNum(stacktop(-2));
0687                     CBigNum bn3 = CastToBigNum(stacktop(-1));
0688                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
0689                     popstack(stack);
0690                     popstack(stack);
0691                     popstack(stack);
0692                     stack.push_back(fValue ? vchTrue : vchFalse);
0693                 }
0694                 break;
0695 
0696 
0697                 //
0698                 // Crypto
0699                 //
0700                 case OP_RIPEMD160:
0701                 case OP_SHA1:
0702                 case OP_SHA256:
0703                 case OP_HASH160:
0704                 case OP_HASH256:
0705                 {
0706                     // (in -- hash)
0707                     if (stack.size() < 1)
0708                         return false;
0709                     valtype& vch = stacktop(-1);
0710                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);
0711                     if (opcode == OP_RIPEMD160)
0712                         RIPEMD160(&vch[0], vch.size(), &vchHash[0]);
0713                     else if (opcode == OP_SHA1)
0714                         SHA1(&vch[0], vch.size(), &vchHash[0]);
0715                     else if (opcode == OP_SHA256)
0716                         SHA256(&vch[0], vch.size(), &vchHash[0]);
0717                     else if (opcode == OP_HASH160)
0718                     {
0719                         uint160 hash160 = Hash160(vch);
0720                         memcpy(&vchHash[0], &hash160, sizeof(hash160));
0721                     }
0722                     else if (opcode == OP_HASH256)
0723                     {
0724                         uint256 hash = Hash(vch.begin(), vch.end());
0725                         memcpy(&vchHash[0], &hash, sizeof(hash));
0726                     }
0727                     popstack(stack);
0728                     stack.push_back(vchHash);
0729                 }
0730                 break;
0731 
0732                 case OP_CODESEPARATOR:
0733                 {
0734                     // Hash starts after the code separator
0735                     pbegincodehash = pc;
0736                 }
0737                 break;
0738 
0739                 case OP_CHECKSIG:
0740                 case OP_CHECKSIGVERIFY:
0741                 {
0742                     // (sig pubkey -- bool)
0743                     if (stack.size() < 2)
0744                         return false;
0745 
0746                     valtype& vchSig    = stacktop(-2);
0747                     valtype& vchPubKey = stacktop(-1);
0748 
0749                     ////// debug print
0750                     //PrintHex(vchSig.begin(), vchSig.end(), "sig: %s\n");
0751                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");
0752 
0753                     // Subset of script starting at the most recent codeseparator
0754                     CScript scriptCode(pbegincodehash, pend);
0755 
0756                     // Drop the signature, since there's no way for a signature to sign itself
0757                     scriptCode.FindAndDelete(CScript(vchSig));
0758 
0759                     bool fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType);
0760 
0761                     popstack(stack);
0762                     popstack(stack);
0763                     stack.push_back(fSuccess ? vchTrue : vchFalse);
0764                     if (opcode == OP_CHECKSIGVERIFY)
0765                     {
0766                         if (fSuccess)
0767                             popstack(stack);
0768                         else
0769                             return false;
0770                     }
0771                 }
0772                 break;
0773 
0774                 case OP_CHECKMULTISIG:
0775                 case OP_CHECKMULTISIGVERIFY:
0776                 {
0777                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
0778 
0779                     int i = 1;
0780                     if (stack.size() < i)
0781                         return false;
0782 
0783                     int nKeysCount = CastToBigNum(stacktop(-i)).getint();
0784                     if (nKeysCount < 0 || nKeysCount > 20)
0785                         return false;
0786                     nOpCount += nKeysCount;
0787                     if (nOpCount > 201)
0788                         return false;
0789                     int ikey = ++i;
0790                     i += nKeysCount;
0791                     if (stack.size() < i)
0792                         return false;
0793 
0794                     int nSigsCount = CastToBigNum(stacktop(-i)).getint();
0795                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
0796                         return false;
0797                     int isig = ++i;
0798                     i += nSigsCount;
0799                     if (stack.size() < i)
0800                         return false;
0801 
0802                     // Subset of script starting at the most recent codeseparator
0803                     CScript scriptCode(pbegincodehash, pend);
0804 
0805                     // Drop the signatures, since there's no way for a signature to sign itself
0806                     for (int k = 0; k < nSigsCount; k++)
0807                     {
0808                         valtype& vchSig = stacktop(-isig-k);
0809                         scriptCode.FindAndDelete(CScript(vchSig));
0810                     }
0811 
0812                     bool fSuccess = true;
0813                     while (fSuccess && nSigsCount > 0)
0814                     {
0815                         valtype& vchSig    = stacktop(-isig);
0816                         valtype& vchPubKey = stacktop(-ikey);
0817 
0818                         // Check signature
0819                         if (CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType))
0820                         {
0821                             isig++;
0822                             nSigsCount--;
0823                         }
0824                         ikey++;
0825                         nKeysCount--;
0826 
0827                         // If there are more signatures left than keys left,
0828                         // then too many signatures have failed
0829                         if (nSigsCount > nKeysCount)
0830                             fSuccess = false;
0831                     }
0832 
0833                     while (i-- > 0)
0834                         popstack(stack);
0835                     stack.push_back(fSuccess ? vchTrue : vchFalse);
0836 
0837                     if (opcode == OP_CHECKMULTISIGVERIFY)
0838                     {
0839                         if (fSuccess)
0840                             popstack(stack);
0841                         else
0842                             return false;
0843                     }
0844                 }
0845                 break;
0846 
0847                 default:
0848                     return false;
0849             }
0850 
0851             // Size limits
0852             if (stack.size() + altstack.size() > 1000)
0853                 return false;
0854         }
0855     }
0856     catch (...)
0857     {
0858         return false;
0859     }
0860 
0861 
0862     if (!vfExec.empty())
0863         return false;
0864 
0865     return true;
0866 }
0867 
0868 
0869 
0870 
0871 
0872 
0873 
0874 
0875 
0876 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
0877 {
0878     if (nIn >= txTo.vin.size())
0879     {
0880         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);
0881         return 1;
0882     }
0883     CTransaction txTmp(txTo);
0884 
0885     // In case concatenating two scripts ends up with two codeseparators,
0886     // or an extra one at the end, this prevents all those possible incompatibilities.
0887     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));
0888 
0889     // Blank out other inputs' signatures
0890     for (int i = 0; i < txTmp.vin.size(); i++)
0891         txTmp.vin[i].scriptSig = CScript();
0892     txTmp.vin[nIn].scriptSig = scriptCode;
0893 
0894     // Blank out some of the outputs
0895     if ((nHashType & 0x1f) == SIGHASH_NONE)
0896     {
0897         // Wildcard payee
0898         txTmp.vout.clear();
0899 
0900         // Let the others update at will
0901         for (int i = 0; i < txTmp.vin.size(); i++)
0902             if (i != nIn)
0903                 txTmp.vin[i].nSequence = 0;
0904     }
0905     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)
0906     {
0907         // Only lockin the txout payee at same index as txin
0908         unsigned int nOut = nIn;
0909         if (nOut >= txTmp.vout.size())
0910         {
0911             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
0912             return 1;
0913         }
0914         txTmp.vout.resize(nOut+1);
0915         for (int i = 0; i < nOut; i++)
0916             txTmp.vout[i].SetNull();
0917 
0918         // Let the others update at will
0919         for (int i = 0; i < txTmp.vin.size(); i++)
0920             if (i != nIn)
0921                 txTmp.vin[i].nSequence = 0;
0922     }
0923 
0924     // Blank out other inputs completely, not recommended for open transactions
0925     if (nHashType & SIGHASH_ANYONECANPAY)
0926     {
0927         txTmp.vin[0] = txTmp.vin[nIn];
0928         txTmp.vin.resize(1);
0929     }
0930 
0931     // Serialize and hash
0932     CDataStream ss(SER_GETHASH);
0933     ss.reserve(10000);
0934     ss << txTmp << nHashType;
0935     return Hash(ss.begin(), ss.end());
0936 }
0937 
0938 
0939 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode,
0940               const CTransaction& txTo, unsigned int nIn, int nHashType)
0941 {
0942     CKey key;
0943     if (!key.SetPubKey(vchPubKey))
0944         return false;
0945 
0946     // Hash type is one byte tacked on to the end of the signature
0947     if (vchSig.empty())
0948         return false;
0949     if (nHashType == 0)
0950         nHashType = vchSig.back();
0951     else if (nHashType != vchSig.back())
0952         return false;
0953     vchSig.pop_back();
0954 
0955     return key.Verify(SignatureHash(scriptCode, txTo, nIn, nHashType), vchSig);
0956 }
0957 
0958 
0959 
0960 
0961 
0962 
0963 
0964 
0965 
0966 
0967 bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSolutionRet)
0968 {
0969     // Templates
0970     static vector<CScript> vTemplates;
0971     if (vTemplates.empty())
0972     {
0973         // Standard tx, sender provides pubkey, receiver adds signature
0974         vTemplates.push_back(CScript() << OP_PUBKEY << OP_CHECKSIG);
0975 
0976         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
0977         vTemplates.push_back(CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG);
0978     }
0979 
0980     // Scan templates
0981     const CScript& script1 = scriptPubKey;
0982     BOOST_FOREACH(const CScript& script2, vTemplates)
0983     {
0984         vSolutionRet.clear();
0985         opcodetype opcode1, opcode2;
0986         vector<unsigned char> vch1, vch2;
0987 
0988         // Compare
0989         CScript::const_iterator pc1 = script1.begin();
0990         CScript::const_iterator pc2 = script2.begin();
0991         loop
0992         {
0993             if (pc1 == script1.end() && pc2 == script2.end())
0994             {
0995                 // Found a match
0996                 reverse(vSolutionRet.begin(), vSolutionRet.end());
0997                 return true;
0998             }
0999             if (!script1.GetOp(pc1, opcode1, vch1))
1000                 break;
1001             if (!script2.GetOp(pc2, opcode2, vch2))
1002                 break;
1003             if (opcode2 == OP_PUBKEY)
1004             {
1005                 if (vch1.size() < 33 || vch1.size() > 120)
1006                     break;
1007                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1008             }
1009             else if (opcode2 == OP_PUBKEYHASH)
1010             {
1011                 if (vch1.size() != sizeof(uint160))
1012                     break;
1013                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1014             }
1015             else if (opcode1 != opcode2 || vch1 != vch2)
1016             {
1017                 break;
1018             }
1019         }
1020     }
1021 
1022     vSolutionRet.clear();
1023     return false;
1024 }
1025 
1026 
1027 bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)
1028 {
1029     scriptSigRet.clear();
1030 
1031     vector<pair<opcodetype, valtype> > vSolution;
1032     if (!Solver(scriptPubKey, vSolution))
1033         return false;
1034 
1035     // Compile solution
1036     BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1037     {
1038         if (item.first == OP_PUBKEY)
1039         {
1040             // Sign
1041             const valtype& vchPubKey = item.second;
1042             CKey key;
1043             if (!keystore.GetKey(Hash160(vchPubKey), key))
1044                 return false;
1045             if (key.GetPubKey() != vchPubKey)
1046                 return false;
1047             if (hash != 0)
1048             {
1049                 vector<unsigned char> vchSig;
1050                 if (!key.Sign(hash, vchSig))
1051                     return false;
1052                 vchSig.push_back((unsigned char)nHashType);
1053                 scriptSigRet << vchSig;
1054             }
1055         }
1056         else if (item.first == OP_PUBKEYHASH)
1057         {
1058             // Sign and give pubkey
1059             CKey key;
1060             if (!keystore.GetKey(uint160(item.second), key))
1061                 return false;
1062             if (hash != 0)
1063             {
1064                 vector<unsigned char> vchSig;
1065                 if (!key.Sign(hash, vchSig))
1066                     return false;
1067                 vchSig.push_back((unsigned char)nHashType);
1068                 scriptSigRet << vchSig << key.GetPubKey();
1069             }
1070         }
1071         else
1072         {
1073             return false;
1074         }
1075     }
1076 
1077     return true;
1078 }
1079 
1080 
1081 bool IsStandard(const CScript& scriptPubKey)
1082 {
1083     vector<pair<opcodetype, valtype> > vSolution;
1084     return Solver(scriptPubKey, vSolution);
1085 }
1086 
1087 
1088 bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey)
1089 {
1090     vector<pair<opcodetype, valtype> > vSolution;
1091     if (!Solver(scriptPubKey, vSolution))
1092         return false;
1093 
1094     // Compile solution
1095     BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1096     {
1097         if (item.first == OP_PUBKEY)
1098         {
1099             const valtype& vchPubKey = item.second;
1100             vector<unsigned char> vchPubKeyFound;
1101             if (!keystore.GetPubKey(Hash160(vchPubKey), vchPubKeyFound))
1102                 return false;
1103             if (vchPubKeyFound != vchPubKey)
1104                 return false;
1105         }
1106         else if (item.first == OP_PUBKEYHASH)
1107         {
1108             if (!keystore.HaveKey(uint160(item.second)))
1109                 return false;
1110         }
1111         else
1112         {
1113             return false;
1114         }
1115     }
1116 
1117     return true;
1118 }
1119 
1120 bool static ExtractAddressInner(const CScript& scriptPubKey, const CKeyStore* keystore, CBitcoinAddress& addressRet)
1121 {
1122     vector<pair<opcodetype, valtype> > vSolution;
1123     if (!Solver(scriptPubKey, vSolution))
1124         return false;
1125 
1126     BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1127     {
1128         if (item.first == OP_PUBKEY)
1129             addressRet.SetPubKey(item.second);
1130         else if (item.first == OP_PUBKEYHASH)
1131             addressRet.SetHash160((uint160)item.second);
1132         if (keystore == NULL || keystore->HaveKey(addressRet))
1133             return true;
1134     }
1135 
1136     return false;
1137 }
1138 
1139 
1140 bool ExtractAddress(const CScript& scriptPubKey, const CKeyStore* keystore, CBitcoinAddress& addressRet)
1141 {
1142     if (keystore)
1143         return ExtractAddressInner(scriptPubKey, keystore, addressRet);
1144     else
1145         return ExtractAddressInner(scriptPubKey, NULL, addressRet);
1146     return false;
1147 }
1148 
1149 
1150 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType)
1151 {
1152     vector<vector<unsigned char> > stack;
1153     if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))
1154         return false;
1155     if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))
1156         return false;
1157     if (stack.empty())
1158         return false;
1159     return CastToBool(stack.back());
1160 }
1161 
1162 
1163 bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType, CScript scriptPrereq)
1164 {
1165     assert(nIn < txTo.vin.size());
1166     CTxIn& txin = txTo.vin[nIn];
1167     assert(txin.prevout.n < txFrom.vout.size());
1168     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1169 
1170     // Leave out the signature from the hash, since a signature can't sign itself.
1171     // The checksig op will also drop the signatures from its hash.
1172     uint256 hash = SignatureHash(scriptPrereq + txout.scriptPubKey, txTo, nIn, nHashType);
1173 
1174     if (!Solver(keystore, txout.scriptPubKey, hash, nHashType, txin.scriptSig))
1175         return false;
1176 
1177     txin.scriptSig = scriptPrereq + txin.scriptSig;
1178 
1179     // Test solution
1180     if (scriptPrereq.empty())
1181         if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, 0))
1182             return false;
1183 
1184     return true;
1185 }
1186 
1187 
1188 bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType)
1189 {
1190     assert(nIn < txTo.vin.size());
1191     const CTxIn& txin = txTo.vin[nIn];
1192     if (txin.prevout.n >= txFrom.vout.size())
1193         return false;
1194     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1195 
1196     if (txin.prevout.hash != txFrom.GetHash())
1197         return false;
1198 
1199     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nHashType))
1200         return false;
1201 
1202     return true;
1203 }