script.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto\r
   2 // Distributed under the MIT/X11 software license, see the accompanying\r
   3 // file license.txt or http://www.opensource.org/licenses/mit-license.php.\r
   4 \r
   5 #include "headers.h"\r
   6 \r
   7 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType);\r
   8 \r
   9 \r
  10 \r
  11 typedef vector<unsigned char> valtype;\r
  12 static const valtype vchFalse(0);\r
  13 static const valtype vchZero(0);\r
  14 static const valtype vchTrue(1, 1);\r
  15 static const CBigNum bnZero(0);\r
  16 static const CBigNum bnOne(1);\r
  17 static const CBigNum bnFalse(0);\r
  18 static const CBigNum bnTrue(1);\r
  19 static const size_t nMaxNumSize = 4;\r
  20 \r
  21 \r
  22 CBigNum CastToBigNum(const valtype& vch)\r
  23 {\r
  24     if (vch.size() > nMaxNumSize)\r
  25         throw runtime_error("CastToBigNum() : overflow");\r
  26     // Get rid of extra leading zeros\r
  27     return CBigNum(CBigNum(vch).getvch());\r
  28 }\r
  29 \r
  30 bool CastToBool(const valtype& vch)\r
  31 {\r
  32     for (int i = 0; i < vch.size(); i++)\r
  33     {\r
  34         if (vch[i] != 0)\r
  35         {\r
  36             // Can be negative zero\r
  37             if (i == vch.size()-1 && vch[i] == 0x80)\r
  38                 return false;\r
  39             return true;\r
  40         }\r
  41     }\r
  42     return false;\r
  43 }\r
  44 \r
  45 void MakeSameSize(valtype& vch1, valtype& vch2)\r
  46 {\r
  47     // Lengthen the shorter one\r
  48     if (vch1.size() < vch2.size())\r
  49         vch1.resize(vch2.size(), 0);\r
  50     if (vch2.size() < vch1.size())\r
  51         vch2.resize(vch1.size(), 0);\r
  52 }\r
  53 \r
  54 \r
  55 \r
  56 //\r
  57 // Script is a stack machine (like Forth) that evaluates a predicate\r
  58 // returning a bool indicating valid or not.  There are no loops.\r
  59 //\r
  60 #define stacktop(i)  (stack.at(stack.size()+(i)))\r
  61 #define altstacktop(i)  (altstack.at(altstack.size()+(i)))\r
  62 \r
  63 bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, int nHashType)\r
  64 {\r
  65     CAutoBN_CTX pctx;\r
  66     CScript::const_iterator pc = script.begin();\r
  67     CScript::const_iterator pend = script.end();\r
  68     CScript::const_iterator pbegincodehash = script.begin();\r
  69     vector<bool> vfExec;\r
  70     vector<valtype> altstack;\r
  71     if (script.size() > 10000)\r
  72         return false;\r
  73     int nOpCount = 0;\r
  74 \r
  75 \r
  76     try\r
  77     {\r
  78         while (pc < pend)\r
  79         {\r
  80             bool fExec = !count(vfExec.begin(), vfExec.end(), false);\r
  81 \r
  82             //\r
  83             // Read instruction\r
  84             //\r
  85             opcodetype opcode;\r
  86             valtype vchPushValue;\r
  87             if (!script.GetOp(pc, opcode, vchPushValue))\r
  88                 return false;\r
  89             if (vchPushValue.size() > 520)\r
  90                 return false;\r
  91             if (opcode > OP_16 && nOpCount++ > 200)\r
  92                 return false;\r
  93 \r
  94             if (opcode == OP_CAT ||\r
  95                 opcode == OP_SUBSTR ||\r
  96                 opcode == OP_LEFT ||\r
  97                 opcode == OP_RIGHT ||\r
  98                 opcode == OP_INVERT ||\r
  99                 opcode == OP_AND ||\r
 100                 opcode == OP_OR ||\r
 101                 opcode == OP_XOR ||\r
 102                 opcode == OP_2MUL ||\r
 103                 opcode == OP_2DIV ||\r
 104                 opcode == OP_MUL ||\r
 105                 opcode == OP_DIV ||\r
 106                 opcode == OP_MOD ||\r
 107                 opcode == OP_LSHIFT ||\r
 108                 opcode == OP_RSHIFT)\r
 109                 return false;\r
 110 \r
 111             if (fExec && opcode <= OP_PUSHDATA4)\r
 112                 stack.push_back(vchPushValue);\r
 113             else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))\r
 114             switch (opcode)\r
 115             {\r
 116                 //\r
 117                 // Push value\r
 118                 //\r
 119                 case OP_1NEGATE:\r
 120                 case OP_1:\r
 121                 case OP_2:\r
 122                 case OP_3:\r
 123                 case OP_4:\r
 124                 case OP_5:\r
 125                 case OP_6:\r
 126                 case OP_7:\r
 127                 case OP_8:\r
 128                 case OP_9:\r
 129                 case OP_10:\r
 130                 case OP_11:\r
 131                 case OP_12:\r
 132                 case OP_13:\r
 133                 case OP_14:\r
 134                 case OP_15:\r
 135                 case OP_16:\r
 136                 {\r
 137                     // ( -- value)\r
 138                     CBigNum bn((int)opcode - (int)(OP_1 - 1));\r
 139                     stack.push_back(bn.getvch());\r
 140                 }\r
 141                 break;\r
 142 \r
 143 \r
 144                 //\r
 145                 // Control\r
 146                 //\r
 147                 case OP_NOP:\r
 148                 case OP_NOP1: case OP_NOP2: case OP_NOP3: case OP_NOP4: case OP_NOP5:\r
 149                 case OP_NOP6: case OP_NOP7: case OP_NOP8: case OP_NOP9: case OP_NOP10:\r
 150                 break;\r
 151 \r
 152                 case OP_VER:\r
 153                 case OP_VERIF:\r
 154                 case OP_VERNOTIF:\r
 155                 {\r
 156                     return false;\r
 157                 }\r
 158                 break;\r
 159 \r
 160                 case OP_IF:\r
 161                 case OP_NOTIF:\r
 162                 {\r
 163                     // <expression> if [statements] [else [statements]] endif\r
 164                     bool fValue = false;\r
 165                     if (fExec)\r
 166                     {\r
 167                         if (stack.size() < 1)\r
 168                             return false;\r
 169                         valtype& vch = stacktop(-1);\r
 170                         fValue = CastToBool(vch);\r
 171                         if (opcode == OP_NOTIF)\r
 172                             fValue = !fValue;\r
 173                         stack.pop_back();\r
 174                     }\r
 175                     vfExec.push_back(fValue);\r
 176                 }\r
 177                 break;\r
 178 \r
 179                 case OP_ELSE:\r
 180                 {\r
 181                     if (vfExec.empty())\r
 182                         return false;\r
 183                     vfExec.back() = !vfExec.back();\r
 184                 }\r
 185                 break;\r
 186 \r
 187                 case OP_ENDIF:\r
 188                 {\r
 189                     if (vfExec.empty())\r
 190                         return false;\r
 191                     vfExec.pop_back();\r
 192                 }\r
 193                 break;\r
 194 \r
 195                 case OP_VERIFY:\r
 196                 {\r
 197                     // (true -- ) or\r
 198                     // (false -- false) and return\r
 199                     if (stack.size() < 1)\r
 200                         return false;\r
 201                     bool fValue = CastToBool(stacktop(-1));\r
 202                     if (fValue)\r
 203                         stack.pop_back();\r
 204                     else\r
 205                         return false;\r
 206                 }\r
 207                 break;\r
 208 \r
 209                 case OP_RETURN:\r
 210                 {\r
 211                     return false;\r
 212                 }\r
 213                 break;\r
 214 \r
 215 \r
 216                 //\r
 217                 // Stack ops\r
 218                 //\r
 219                 case OP_TOALTSTACK:\r
 220                 {\r
 221                     if (stack.size() < 1)\r
 222                         return false;\r
 223                     altstack.push_back(stacktop(-1));\r
 224                     stack.pop_back();\r
 225                 }\r
 226                 break;\r
 227 \r
 228                 case OP_FROMALTSTACK:\r
 229                 {\r
 230                     if (altstack.size() < 1)\r
 231                         return false;\r
 232                     stack.push_back(altstacktop(-1));\r
 233                     altstack.pop_back();\r
 234                 }\r
 235                 break;\r
 236 \r
 237                 case OP_2DROP:\r
 238                 {\r
 239                     // (x1 x2 -- )\r
 240                     stack.pop_back();\r
 241                     stack.pop_back();\r
 242                 }\r
 243                 break;\r
 244 \r
 245                 case OP_2DUP:\r
 246                 {\r
 247                     // (x1 x2 -- x1 x2 x1 x2)\r
 248                     if (stack.size() < 2)\r
 249                         return false;\r
 250                     valtype vch1 = stacktop(-2);\r
 251                     valtype vch2 = stacktop(-1);\r
 252                     stack.push_back(vch1);\r
 253                     stack.push_back(vch2);\r
 254                 }\r
 255                 break;\r
 256 \r
 257                 case OP_3DUP:\r
 258                 {\r
 259                     // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)\r
 260                     if (stack.size() < 3)\r
 261                         return false;\r
 262                     valtype vch1 = stacktop(-3);\r
 263                     valtype vch2 = stacktop(-2);\r
 264                     valtype vch3 = stacktop(-1);\r
 265                     stack.push_back(vch1);\r
 266                     stack.push_back(vch2);\r
 267                     stack.push_back(vch3);\r
 268                 }\r
 269                 break;\r
 270 \r
 271                 case OP_2OVER:\r
 272                 {\r
 273                     // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)\r
 274                     if (stack.size() < 4)\r
 275                         return false;\r
 276                     valtype vch1 = stacktop(-4);\r
 277                     valtype vch2 = stacktop(-3);\r
 278                     stack.push_back(vch1);\r
 279                     stack.push_back(vch2);\r
 280                 }\r
 281                 break;\r
 282 \r
 283                 case OP_2ROT:\r
 284                 {\r
 285                     // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)\r
 286                     if (stack.size() < 6)\r
 287                         return false;\r
 288                     valtype vch1 = stacktop(-6);\r
 289                     valtype vch2 = stacktop(-5);\r
 290                     stack.erase(stack.end()-6, stack.end()-4);\r
 291                     stack.push_back(vch1);\r
 292                     stack.push_back(vch2);\r
 293                 }\r
 294                 break;\r
 295 \r
 296                 case OP_2SWAP:\r
 297                 {\r
 298                     // (x1 x2 x3 x4 -- x3 x4 x1 x2)\r
 299                     if (stack.size() < 4)\r
 300                         return false;\r
 301                     swap(stacktop(-4), stacktop(-2));\r
 302                     swap(stacktop(-3), stacktop(-1));\r
 303                 }\r
 304                 break;\r
 305 \r
 306                 case OP_IFDUP:\r
 307                 {\r
 308                     // (x - 0 | x x)\r
 309                     if (stack.size() < 1)\r
 310                         return false;\r
 311                     valtype vch = stacktop(-1);\r
 312                     if (CastToBool(vch))\r
 313                         stack.push_back(vch);\r
 314                 }\r
 315                 break;\r
 316 \r
 317                 case OP_DEPTH:\r
 318                 {\r
 319                     // -- stacksize\r
 320                     CBigNum bn(stack.size());\r
 321                     stack.push_back(bn.getvch());\r
 322                 }\r
 323                 break;\r
 324 \r
 325                 case OP_DROP:\r
 326                 {\r
 327                     // (x -- )\r
 328                     if (stack.size() < 1)\r
 329                         return false;\r
 330                     stack.pop_back();\r
 331                 }\r
 332                 break;\r
 333 \r
 334                 case OP_DUP:\r
 335                 {\r
 336                     // (x -- x x)\r
 337                     if (stack.size() < 1)\r
 338                         return false;\r
 339                     valtype vch = stacktop(-1);\r
 340                     stack.push_back(vch);\r
 341                 }\r
 342                 break;\r
 343 \r
 344                 case OP_NIP:\r
 345                 {\r
 346                     // (x1 x2 -- x2)\r
 347                     if (stack.size() < 2)\r
 348                         return false;\r
 349                     stack.erase(stack.end() - 2);\r
 350                 }\r
 351                 break;\r
 352 \r
 353                 case OP_OVER:\r
 354                 {\r
 355                     // (x1 x2 -- x1 x2 x1)\r
 356                     if (stack.size() < 2)\r
 357                         return false;\r
 358                     valtype vch = stacktop(-2);\r
 359                     stack.push_back(vch);\r
 360                 }\r
 361                 break;\r
 362 \r
 363                 case OP_PICK:\r
 364                 case OP_ROLL:\r
 365                 {\r
 366                     // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)\r
 367                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)\r
 368                     if (stack.size() < 2)\r
 369                         return false;\r
 370                     int n = CastToBigNum(stacktop(-1)).getint();\r
 371                     stack.pop_back();\r
 372                     if (n < 0 || n >= stack.size())\r
 373                         return false;\r
 374                     valtype vch = stacktop(-n-1);\r
 375                     if (opcode == OP_ROLL)\r
 376                         stack.erase(stack.end()-n-1);\r
 377                     stack.push_back(vch);\r
 378                 }\r
 379                 break;\r
 380 \r
 381                 case OP_ROT:\r
 382                 {\r
 383                     // (x1 x2 x3 -- x2 x3 x1)\r
 384                     //  x2 x1 x3  after first swap\r
 385                     //  x2 x3 x1  after second swap\r
 386                     if (stack.size() < 3)\r
 387                         return false;\r
 388                     swap(stacktop(-3), stacktop(-2));\r
 389                     swap(stacktop(-2), stacktop(-1));\r
 390                 }\r
 391                 break;\r
 392 \r
 393                 case OP_SWAP:\r
 394                 {\r
 395                     // (x1 x2 -- x2 x1)\r
 396                     if (stack.size() < 2)\r
 397                         return false;\r
 398                     swap(stacktop(-2), stacktop(-1));\r
 399                 }\r
 400                 break;\r
 401 \r
 402                 case OP_TUCK:\r
 403                 {\r
 404                     // (x1 x2 -- x2 x1 x2)\r
 405                     if (stack.size() < 2)\r
 406                         return false;\r
 407                     valtype vch = stacktop(-1);\r
 408                     stack.insert(stack.end()-2, vch);\r
 409                 }\r
 410                 break;\r
 411 \r
 412 \r
 413                 //\r
 414                 // Splice ops\r
 415                 //\r
 416                 case OP_CAT:\r
 417                 {\r
 418                     // (x1 x2 -- out)\r
 419                     if (stack.size() < 2)\r
 420                         return false;\r
 421                     valtype& vch1 = stacktop(-2);\r
 422                     valtype& vch2 = stacktop(-1);\r
 423                     vch1.insert(vch1.end(), vch2.begin(), vch2.end());\r
 424                     stack.pop_back();\r
 425                     if (stacktop(-1).size() > 520)\r
 426                         return false;\r
 427                 }\r
 428                 break;\r
 429 \r
 430                 case OP_SUBSTR:\r
 431                 {\r
 432                     // (in begin size -- out)\r
 433                     if (stack.size() < 3)\r
 434                         return false;\r
 435                     valtype& vch = stacktop(-3);\r
 436                     int nBegin = CastToBigNum(stacktop(-2)).getint();\r
 437                     int nEnd = nBegin + CastToBigNum(stacktop(-1)).getint();\r
 438                     if (nBegin < 0 || nEnd < nBegin)\r
 439                         return false;\r
 440                     if (nBegin > vch.size())\r
 441                         nBegin = vch.size();\r
 442                     if (nEnd > vch.size())\r
 443                         nEnd = vch.size();\r
 444                     vch.erase(vch.begin() + nEnd, vch.end());\r
 445                     vch.erase(vch.begin(), vch.begin() + nBegin);\r
 446                     stack.pop_back();\r
 447                     stack.pop_back();\r
 448                 }\r
 449                 break;\r
 450 \r
 451                 case OP_LEFT:\r
 452                 case OP_RIGHT:\r
 453                 {\r
 454                     // (in size -- out)\r
 455                     if (stack.size() < 2)\r
 456                         return false;\r
 457                     valtype& vch = stacktop(-2);\r
 458                     int nSize = CastToBigNum(stacktop(-1)).getint();\r
 459                     if (nSize < 0)\r
 460                         return false;\r
 461                     if (nSize > vch.size())\r
 462                         nSize = vch.size();\r
 463                     if (opcode == OP_LEFT)\r
 464                         vch.erase(vch.begin() + nSize, vch.end());\r
 465                     else\r
 466                         vch.erase(vch.begin(), vch.end() - nSize);\r
 467                     stack.pop_back();\r
 468                 }\r
 469                 break;\r
 470 \r
 471                 case OP_SIZE:\r
 472                 {\r
 473                     // (in -- in size)\r
 474                     if (stack.size() < 1)\r
 475                         return false;\r
 476                     CBigNum bn(stacktop(-1).size());\r
 477                     stack.push_back(bn.getvch());\r
 478                 }\r
 479                 break;\r
 480 \r
 481 \r
 482                 //\r
 483                 // Bitwise logic\r
 484                 //\r
 485                 case OP_INVERT:\r
 486                 {\r
 487                     // (in - out)\r
 488                     if (stack.size() < 1)\r
 489                         return false;\r
 490                     valtype& vch = stacktop(-1);\r
 491                     for (int i = 0; i < vch.size(); i++)\r
 492                         vch[i] = ~vch[i];\r
 493                 }\r
 494                 break;\r
 495 \r
 496                 case OP_AND:\r
 497                 case OP_OR:\r
 498                 case OP_XOR:\r
 499                 {\r
 500                     // (x1 x2 - out)\r
 501                     if (stack.size() < 2)\r
 502                         return false;\r
 503                     valtype& vch1 = stacktop(-2);\r
 504                     valtype& vch2 = stacktop(-1);\r
 505                     MakeSameSize(vch1, vch2);\r
 506                     if (opcode == OP_AND)\r
 507                     {\r
 508                         for (int i = 0; i < vch1.size(); i++)\r
 509                             vch1[i] &= vch2[i];\r
 510                     }\r
 511                     else if (opcode == OP_OR)\r
 512                     {\r
 513                         for (int i = 0; i < vch1.size(); i++)\r
 514                             vch1[i] |= vch2[i];\r
 515                     }\r
 516                     else if (opcode == OP_XOR)\r
 517                     {\r
 518                         for (int i = 0; i < vch1.size(); i++)\r
 519                             vch1[i] ^= vch2[i];\r
 520                     }\r
 521                     stack.pop_back();\r
 522                 }\r
 523                 break;\r
 524 \r
 525                 case OP_EQUAL:\r
 526                 case OP_EQUALVERIFY:\r
 527                 //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL\r
 528                 {\r
 529                     // (x1 x2 - bool)\r
 530                     if (stack.size() < 2)\r
 531                         return false;\r
 532                     valtype& vch1 = stacktop(-2);\r
 533                     valtype& vch2 = stacktop(-1);\r
 534                     bool fEqual = (vch1 == vch2);\r
 535                     // OP_NOTEQUAL is disabled because it would be too easy to say\r
 536                     // something like n != 1 and have some wiseguy pass in 1 with extra\r
 537                     // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)\r
 538                     //if (opcode == OP_NOTEQUAL)\r
 539                     //    fEqual = !fEqual;\r
 540                     stack.pop_back();\r
 541                     stack.pop_back();\r
 542                     stack.push_back(fEqual ? vchTrue : vchFalse);\r
 543                     if (opcode == OP_EQUALVERIFY)\r
 544                     {\r
 545                         if (fEqual)\r
 546                             stack.pop_back();\r
 547                         else\r
 548                             return false;\r
 549                     }\r
 550                 }\r
 551                 break;\r
 552 \r
 553 \r
 554                 //\r
 555                 // Numeric\r
 556                 //\r
 557                 case OP_1ADD:\r
 558                 case OP_1SUB:\r
 559                 case OP_2MUL:\r
 560                 case OP_2DIV:\r
 561                 case OP_NEGATE:\r
 562                 case OP_ABS:\r
 563                 case OP_NOT:\r
 564                 case OP_0NOTEQUAL:\r
 565                 {\r
 566                     // (in -- out)\r
 567                     if (stack.size() < 1)\r
 568                         return false;\r
 569                     CBigNum bn = CastToBigNum(stacktop(-1));\r
 570                     switch (opcode)\r
 571                     {\r
 572                     case OP_1ADD:       bn += bnOne; break;\r
 573                     case OP_1SUB:       bn -= bnOne; break;\r
 574                     case OP_2MUL:       bn <<= 1; break;\r
 575                     case OP_2DIV:       bn >>= 1; break;\r
 576                     case OP_NEGATE:     bn = -bn; break;\r
 577                     case OP_ABS:        if (bn < bnZero) bn = -bn; break;\r
 578                     case OP_NOT:        bn = (bn == bnZero); break;\r
 579                     case OP_0NOTEQUAL:  bn = (bn != bnZero); break;\r
 580                     }\r
 581                     stack.pop_back();\r
 582                     stack.push_back(bn.getvch());\r
 583                 }\r
 584                 break;\r
 585 \r
 586                 case OP_ADD:\r
 587                 case OP_SUB:\r
 588                 case OP_MUL:\r
 589                 case OP_DIV:\r
 590                 case OP_MOD:\r
 591                 case OP_LSHIFT:\r
 592                 case OP_RSHIFT:\r
 593                 case OP_BOOLAND:\r
 594                 case OP_BOOLOR:\r
 595                 case OP_NUMEQUAL:\r
 596                 case OP_NUMEQUALVERIFY:\r
 597                 case OP_NUMNOTEQUAL:\r
 598                 case OP_LESSTHAN:\r
 599                 case OP_GREATERTHAN:\r
 600                 case OP_LESSTHANOREQUAL:\r
 601                 case OP_GREATERTHANOREQUAL:\r
 602                 case OP_MIN:\r
 603                 case OP_MAX:\r
 604                 {\r
 605                     // (x1 x2 -- out)\r
 606                     if (stack.size() < 2)\r
 607                         return false;\r
 608                     CBigNum bn1 = CastToBigNum(stacktop(-2));\r
 609                     CBigNum bn2 = CastToBigNum(stacktop(-1));\r
 610                     CBigNum bn;\r
 611                     switch (opcode)\r
 612                     {\r
 613                     case OP_ADD:\r
 614                         bn = bn1 + bn2;\r
 615                         break;\r
 616 \r
 617                     case OP_SUB:\r
 618                         bn = bn1 - bn2;\r
 619                         break;\r
 620 \r
 621                     case OP_MUL:\r
 622                         if (!BN_mul(&bn, &bn1, &bn2, pctx))\r
 623                             return false;\r
 624                         break;\r
 625 \r
 626                     case OP_DIV:\r
 627                         if (!BN_div(&bn, NULL, &bn1, &bn2, pctx))\r
 628                             return false;\r
 629                         break;\r
 630 \r
 631                     case OP_MOD:\r
 632                         if (!BN_mod(&bn, &bn1, &bn2, pctx))\r
 633                             return false;\r
 634                         break;\r
 635 \r
 636                     case OP_LSHIFT:\r
 637                         if (bn2 < bnZero || bn2 > CBigNum(2048))\r
 638                             return false;\r
 639                         bn = bn1 << bn2.getulong();\r
 640                         break;\r
 641 \r
 642                     case OP_RSHIFT:\r
 643                         if (bn2 < bnZero || bn2 > CBigNum(2048))\r
 644                             return false;\r
 645                         bn = bn1 >> bn2.getulong();\r
 646                         break;\r
 647 \r
 648                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;\r
 649                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;\r
 650                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;\r
 651                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;\r
 652                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;\r
 653                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;\r
 654                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;\r
 655                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;\r
 656                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;\r
 657                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;\r
 658                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;\r
 659                     }\r
 660                     stack.pop_back();\r
 661                     stack.pop_back();\r
 662                     stack.push_back(bn.getvch());\r
 663 \r
 664                     if (opcode == OP_NUMEQUALVERIFY)\r
 665                     {\r
 666                         if (CastToBool(stacktop(-1)))\r
 667                             stack.pop_back();\r
 668                         else\r
 669                             return false;\r
 670                     }\r
 671                 }\r
 672                 break;\r
 673 \r
 674                 case OP_WITHIN:\r
 675                 {\r
 676                     // (x min max -- out)\r
 677                     if (stack.size() < 3)\r
 678                         return false;\r
 679                     CBigNum bn1 = CastToBigNum(stacktop(-3));\r
 680                     CBigNum bn2 = CastToBigNum(stacktop(-2));\r
 681                     CBigNum bn3 = CastToBigNum(stacktop(-1));\r
 682                     bool fValue = (bn2 <= bn1 && bn1 < bn3);\r
 683                     stack.pop_back();\r
 684                     stack.pop_back();\r
 685                     stack.pop_back();\r
 686                     stack.push_back(fValue ? vchTrue : vchFalse);\r
 687                 }\r
 688                 break;\r
 689 \r
 690 \r
 691                 //\r
 692                 // Crypto\r
 693                 //\r
 694                 case OP_RIPEMD160:\r
 695                 case OP_SHA1:\r
 696                 case OP_SHA256:\r
 697                 case OP_HASH160:\r
 698                 case OP_HASH256:\r
 699                 {\r
 700                     // (in -- hash)\r
 701                     if (stack.size() < 1)\r
 702                         return false;\r
 703                     valtype& vch = stacktop(-1);\r
 704                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);\r
 705                     if (opcode == OP_RIPEMD160)\r
 706                         RIPEMD160(&vch[0], vch.size(), &vchHash[0]);\r
 707                     else if (opcode == OP_SHA1)\r
 708                         SHA1(&vch[0], vch.size(), &vchHash[0]);\r
 709                     else if (opcode == OP_SHA256)\r
 710                         SHA256(&vch[0], vch.size(), &vchHash[0]);\r
 711                     else if (opcode == OP_HASH160)\r
 712                     {\r
 713                         uint160 hash160 = Hash160(vch);\r
 714                         memcpy(&vchHash[0], &hash160, sizeof(hash160));\r
 715                     }\r
 716                     else if (opcode == OP_HASH256)\r
 717                     {\r
 718                         uint256 hash = Hash(vch.begin(), vch.end());\r
 719                         memcpy(&vchHash[0], &hash, sizeof(hash));\r
 720                     }\r
 721                     stack.pop_back();\r
 722                     stack.push_back(vchHash);\r
 723                 }\r
 724                 break;\r
 725 \r
 726                 case OP_CODESEPARATOR:\r
 727                 {\r
 728                     // Hash starts after the code separator\r
 729                     pbegincodehash = pc;\r
 730                 }\r
 731                 break;\r
 732 \r
 733                 case OP_CHECKSIG:\r
 734                 case OP_CHECKSIGVERIFY:\r
 735                 {\r
 736                     // (sig pubkey -- bool)\r
 737                     if (stack.size() < 2)\r
 738                         return false;\r
 739 \r
 740                     valtype& vchSig    = stacktop(-2);\r
 741                     valtype& vchPubKey = stacktop(-1);\r
 742 \r
 743                     ////// debug print\r
 744                     //PrintHex(vchSig.begin(), vchSig.end(), "sig: %s\n");\r
 745                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");\r
 746 \r
 747                     // Subset of script starting at the most recent codeseparator\r
 748                     CScript scriptCode(pbegincodehash, pend);\r
 749 \r
 750                     // Drop the signature, since there's no way for a signature to sign itself\r
 751                     scriptCode.FindAndDelete(CScript(vchSig));\r
 752 \r
 753                     bool fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType);\r
 754 \r
 755                     stack.pop_back();\r
 756                     stack.pop_back();\r
 757                     stack.push_back(fSuccess ? vchTrue : vchFalse);\r
 758                     if (opcode == OP_CHECKSIGVERIFY)\r
 759                     {\r
 760                         if (fSuccess)\r
 761                             stack.pop_back();\r
 762                         else\r
 763                             return false;\r
 764                     }\r
 765                 }\r
 766                 break;\r
 767 \r
 768                 case OP_CHECKMULTISIG:\r
 769                 case OP_CHECKMULTISIGVERIFY:\r
 770                 {\r
 771                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)\r
 772 \r
 773                     int i = 1;\r
 774                     if (stack.size() < i)\r
 775                         return false;\r
 776 \r
 777                     int nKeysCount = CastToBigNum(stacktop(-i)).getint();\r
 778                     if (nKeysCount < 0)\r
 779                         return false;\r
 780                     int ikey = ++i;\r
 781                     i += nKeysCount;\r
 782                     if (stack.size() < i)\r
 783                         return false;\r
 784 \r
 785                     int nSigsCount = CastToBigNum(stacktop(-i)).getint();\r
 786                     if (nSigsCount < 0 || nSigsCount > nKeysCount)\r
 787                         return false;\r
 788                     int isig = ++i;\r
 789                     i += nSigsCount;\r
 790                     if (stack.size() < i)\r
 791                         return false;\r
 792 \r
 793                     // Subset of script starting at the most recent codeseparator\r
 794                     CScript scriptCode(pbegincodehash, pend);\r
 795 \r
 796                     // Drop the signatures, since there's no way for a signature to sign itself\r
 797                     for (int k = 0; k < nSigsCount; k++)\r
 798                     {\r
 799                         valtype& vchSig = stacktop(-isig-k);\r
 800                         scriptCode.FindAndDelete(CScript(vchSig));\r
 801                     }\r
 802 \r
 803                     bool fSuccess = true;\r
 804                     while (fSuccess && nSigsCount > 0)\r
 805                     {\r
 806                         valtype& vchSig    = stacktop(-isig);\r
 807                         valtype& vchPubKey = stacktop(-ikey);\r
 808 \r
 809                         // Check signature\r
 810                         if (CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType))\r
 811                         {\r
 812                             isig++;\r
 813                             nSigsCount--;\r
 814                         }\r
 815                         ikey++;\r
 816                         nKeysCount--;\r
 817 \r
 818                         // If there are more signatures left than keys left,\r
 819                         // then too many signatures have failed\r
 820                         if (nSigsCount > nKeysCount)\r
 821                             fSuccess = false;\r
 822                     }\r
 823 \r
 824                     while (i-- > 0)\r
 825                         stack.pop_back();\r
 826                     stack.push_back(fSuccess ? vchTrue : vchFalse);\r
 827 \r
 828                     if (opcode == OP_CHECKMULTISIGVERIFY)\r
 829                     {\r
 830                         if (fSuccess)\r
 831                             stack.pop_back();\r
 832                         else\r
 833                             return false;\r
 834                     }\r
 835                 }\r
 836                 break;\r
 837 \r
 838                 default:\r
 839                     return false;\r
 840             }\r
 841 \r
 842             // Size limits\r
 843             if (stack.size() + altstack.size() > 1000)\r
 844                 return false;\r
 845         }\r
 846     }\r
 847     catch (...)\r
 848     {\r
 849         return false;\r
 850     }\r
 851 \r
 852 \r
 853     if (!vfExec.empty())\r
 854         return false;\r
 855 \r
 856     return true;\r
 857 }\r
 858 \r
 859 #undef top\r
 860 \r
 861 \r
 862 \r
 863 \r
 864 \r
 865 \r
 866 \r
 867 \r
 868 \r
 869 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)\r
 870 {\r
 871     if (nIn >= txTo.vin.size())\r
 872     {\r
 873         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);\r
 874         return 1;\r
 875     }\r
 876     CTransaction txTmp(txTo);\r
 877 \r
 878     // In case concatenating two scripts ends up with two codeseparators,\r
 879     // or an extra one at the end, this prevents all those possible incompatibilities.\r
 880     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));\r
 881 \r
 882     // Blank out other inputs' signatures\r
 883     for (int i = 0; i < txTmp.vin.size(); i++)\r
 884         txTmp.vin[i].scriptSig = CScript();\r
 885     txTmp.vin[nIn].scriptSig = scriptCode;\r
 886 \r
 887     // Blank out some of the outputs\r
 888     if ((nHashType & 0x1f) == SIGHASH_NONE)\r
 889     {\r
 890         // Wildcard payee\r
 891         txTmp.vout.clear();\r
 892 \r
 893         // Let the others update at will\r
 894         for (int i = 0; i < txTmp.vin.size(); i++)\r
 895             if (i != nIn)\r
 896                 txTmp.vin[i].nSequence = 0;\r
 897     }\r
 898     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)\r
 899     {\r
 900         // Only lockin the txout payee at same index as txin\r
 901         unsigned int nOut = nIn;\r
 902         if (nOut >= txTmp.vout.size())\r
 903         {\r
 904             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);\r
 905             return 1;\r
 906         }\r
 907         txTmp.vout.resize(nOut+1);\r
 908         for (int i = 0; i < nOut; i++)\r
 909             txTmp.vout[i].SetNull();\r
 910 \r
 911         // Let the others update at will\r
 912         for (int i = 0; i < txTmp.vin.size(); i++)\r
 913             if (i != nIn)\r
 914                 txTmp.vin[i].nSequence = 0;\r
 915     }\r
 916 \r
 917     // Blank out other inputs completely, not recommended for open transactions\r
 918     if (nHashType & SIGHASH_ANYONECANPAY)\r
 919     {\r
 920         txTmp.vin[0] = txTmp.vin[nIn];\r
 921         txTmp.vin.resize(1);\r
 922     }\r
 923 \r
 924     // Serialize and hash\r
 925     CDataStream ss(SER_GETHASH);\r
 926     ss.reserve(10000);\r
 927     ss << txTmp << nHashType;\r
 928     return Hash(ss.begin(), ss.end());\r
 929 }\r
 930 \r
 931 \r
 932 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode,\r
 933               const CTransaction& txTo, unsigned int nIn, int nHashType)\r
 934 {\r
 935     CKey key;\r
 936     if (!key.SetPubKey(vchPubKey))\r
 937         return false;\r
 938 \r
 939     // Hash type is one byte tacked on to the end of the signature\r
 940     if (vchSig.empty())\r
 941         return false;\r
 942     if (nHashType == 0)\r
 943         nHashType = vchSig.back();\r
 944     else if (nHashType != vchSig.back())\r
 945         return false;\r
 946     vchSig.pop_back();\r
 947 \r
 948     if (key.Verify(SignatureHash(scriptCode, txTo, nIn, nHashType), vchSig))\r
 949         return true;\r
 950 \r
 951     return false;\r
 952 }\r
 953 \r
 954 \r
 955 \r
 956 \r
 957 \r
 958 \r
 959 \r
 960 \r
 961 \r
 962 \r
 963 bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSolutionRet)\r
 964 {\r
 965     // Templates\r
 966     static vector<CScript> vTemplates;\r
 967     if (vTemplates.empty())\r
 968     {\r
 969         // Standard tx, sender provides pubkey, receiver adds signature\r
 970         vTemplates.push_back(CScript() << OP_PUBKEY << OP_CHECKSIG);\r
 971 \r
 972         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey\r
 973         vTemplates.push_back(CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG);\r
 974     }\r
 975 \r
 976     // Scan templates\r
 977     const CScript& script1 = scriptPubKey;\r
 978     foreach(const CScript& script2, vTemplates)\r
 979     {\r
 980         vSolutionRet.clear();\r
 981         opcodetype opcode1, opcode2;\r
 982         vector<unsigned char> vch1, vch2;\r
 983 \r
 984         // Compare\r
 985         CScript::const_iterator pc1 = script1.begin();\r
 986         CScript::const_iterator pc2 = script2.begin();\r
 987         loop\r
 988         {\r
 989             bool f1 = script1.GetOp(pc1, opcode1, vch1);\r
 990             bool f2 = script2.GetOp(pc2, opcode2, vch2);\r
 991             if (!f1 && !f2)\r
 992             {\r
 993                 // Success\r
 994                 reverse(vSolutionRet.begin(), vSolutionRet.end());\r
 995                 return true;\r
 996             }\r
 997             else if (f1 != f2)\r
 998             {\r
 999                 break;\r
1000             }\r
1001             else if (opcode2 == OP_PUBKEY)\r
1002             {\r
1003                 if (vch1.size() <= sizeof(uint256))\r
1004                     break;\r
1005                 vSolutionRet.push_back(make_pair(opcode2, vch1));\r
1006             }\r
1007             else if (opcode2 == OP_PUBKEYHASH)\r
1008             {\r
1009                 if (vch1.size() != sizeof(uint160))\r
1010                     break;\r
1011                 vSolutionRet.push_back(make_pair(opcode2, vch1));\r
1012             }\r
1013             else if (opcode1 != opcode2)\r
1014             {\r
1015                 break;\r
1016             }\r
1017         }\r
1018     }\r
1019 \r
1020     vSolutionRet.clear();\r
1021     return false;\r
1022 }\r
1023 \r
1024 \r
1025 bool Solver(const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)\r
1026 {\r
1027     scriptSigRet.clear();\r
1028 \r
1029     vector<pair<opcodetype, valtype> > vSolution;\r
1030     if (!Solver(scriptPubKey, vSolution))\r
1031         return false;\r
1032 \r
1033     // Compile solution\r
1034     CRITICAL_BLOCK(cs_mapKeys)\r
1035     {\r
1036         foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)\r
1037         {\r
1038             if (item.first == OP_PUBKEY)\r
1039             {\r
1040                 // Sign\r
1041                 const valtype& vchPubKey = item.second;\r
1042                 if (!mapKeys.count(vchPubKey))\r
1043                     return false;\r
1044                 if (hash != 0)\r
1045                 {\r
1046                     vector<unsigned char> vchSig;\r
1047                     if (!CKey::Sign(mapKeys[vchPubKey], hash, vchSig))\r
1048                         return false;\r
1049                     vchSig.push_back((unsigned char)nHashType);\r
1050                     scriptSigRet << vchSig;\r
1051                 }\r
1052             }\r
1053             else if (item.first == OP_PUBKEYHASH)\r
1054             {\r
1055                 // Sign and give pubkey\r
1056                 map<uint160, valtype>::iterator mi = mapPubKeys.find(uint160(item.second));\r
1057                 if (mi == mapPubKeys.end())\r
1058                     return false;\r
1059                 const vector<unsigned char>& vchPubKey = (*mi).second;\r
1060                 if (!mapKeys.count(vchPubKey))\r
1061                     return false;\r
1062                 if (hash != 0)\r
1063                 {\r
1064                     vector<unsigned char> vchSig;\r
1065                     if (!CKey::Sign(mapKeys[vchPubKey], hash, vchSig))\r
1066                         return false;\r
1067                     vchSig.push_back((unsigned char)nHashType);\r
1068                     scriptSigRet << vchSig << vchPubKey;\r
1069                 }\r
1070             }\r
1071         }\r
1072     }\r
1073 \r
1074     return true;\r
1075 }\r
1076 \r
1077 \r
1078 bool IsMine(const CScript& scriptPubKey)\r
1079 {\r
1080     CScript scriptSig;\r
1081     return Solver(scriptPubKey, 0, 0, scriptSig);\r
1082 }\r
1083 \r
1084 \r
1085 bool ExtractPubKey(const CScript& scriptPubKey, bool fMineOnly, vector<unsigned char>& vchPubKeyRet)\r
1086 {\r
1087     vchPubKeyRet.clear();\r
1088 \r
1089     vector<pair<opcodetype, valtype> > vSolution;\r
1090     if (!Solver(scriptPubKey, vSolution))\r
1091         return false;\r
1092 \r
1093     CRITICAL_BLOCK(cs_mapKeys)\r
1094     {\r
1095         foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)\r
1096         {\r
1097             valtype vchPubKey;\r
1098             if (item.first == OP_PUBKEY)\r
1099             {\r
1100                 vchPubKey = item.second;\r
1101             }\r
1102             else if (item.first == OP_PUBKEYHASH)\r
1103             {\r
1104                 map<uint160, valtype>::iterator mi = mapPubKeys.find(uint160(item.second));\r
1105                 if (mi == mapPubKeys.end())\r
1106                     continue;\r
1107                 vchPubKey = (*mi).second;\r
1108             }\r
1109             if (!fMineOnly || mapKeys.count(vchPubKey))\r
1110             {\r
1111                 vchPubKeyRet = vchPubKey;\r
1112                 return true;\r
1113             }\r
1114         }\r
1115     }\r
1116     return false;\r
1117 }\r
1118 \r
1119 \r
1120 bool ExtractHash160(const CScript& scriptPubKey, uint160& hash160Ret)\r
1121 {\r
1122     hash160Ret = 0;\r
1123 \r
1124     vector<pair<opcodetype, valtype> > vSolution;\r
1125     if (!Solver(scriptPubKey, vSolution))\r
1126         return false;\r
1127 \r
1128     foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)\r
1129     {\r
1130         if (item.first == OP_PUBKEYHASH)\r
1131         {\r
1132             hash160Ret = uint160(item.second);\r
1133             return true;\r
1134         }\r
1135     }\r
1136     return false;\r
1137 }\r
1138 \r
1139 \r
1140 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType)\r
1141 {\r
1142     vector<vector<unsigned char> > stack;\r
1143     if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))\r
1144         return false;\r
1145     if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))\r
1146         return false;\r
1147     if (stack.empty())\r
1148         return false;\r
1149     return CastToBool(stack.back());\r
1150 }\r
1151 \r
1152 \r
1153 bool SignSignature(const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType, CScript scriptPrereq)\r
1154 {\r
1155     assert(nIn < txTo.vin.size());\r
1156     CTxIn& txin = txTo.vin[nIn];\r
1157     assert(txin.prevout.n < txFrom.vout.size());\r
1158     const CTxOut& txout = txFrom.vout[txin.prevout.n];\r
1159 \r
1160     // Leave out the signature from the hash, since a signature can't sign itself.\r
1161     // The checksig op will also drop the signatures from its hash.\r
1162     uint256 hash = SignatureHash(scriptPrereq + txout.scriptPubKey, txTo, nIn, nHashType);\r
1163 \r
1164     if (!Solver(txout.scriptPubKey, hash, nHashType, txin.scriptSig))\r
1165         return false;\r
1166 \r
1167     txin.scriptSig = scriptPrereq + txin.scriptSig;\r
1168 \r
1169     // Test solution\r
1170     if (scriptPrereq.empty())\r
1171         if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, 0))\r
1172             return false;\r
1173 \r
1174     return true;\r
1175 }\r
1176 \r
1177 \r
1178 bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType)\r
1179 {\r
1180     assert(nIn < txTo.vin.size());\r
1181     const CTxIn& txin = txTo.vin[nIn];\r
1182     if (txin.prevout.n >= txFrom.vout.size())\r
1183         return false;\r
1184     const CTxOut& txout = txFrom.vout[txin.prevout.n];\r
1185 \r
1186     if (txin.prevout.hash != txFrom.GetHash())\r
1187         return false;\r
1188 \r
1189     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nHashType))\r
1190         return false;\r
1191 \r
1192     // Anytime a signature is successfully verified, it's proof the outpoint is spent,\r
1193     // so lets update the wallet spent flag if it doesn't know due to wallet.dat being\r
1194     // restored from backup or the user making copies of wallet.dat.\r
1195     WalletUpdateSpent(txin.prevout);\r
1196 \r
1197     return true;\r
1198 }\r