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