BIP141: Witness program

8 files changed, 163 insertions, 6 deletions

diff --git a/src/script/bitcoinconsensus.cpp b/src/script/bitcoinconsensus.cpp
index 47ad1d0807..5c9e7c0a57 100644
--- a/src/script/bitcoinconsensus.cpp
+++ b/src/script/bitcoinconsensus.cpp
@@ -85,7 +85,7 @@ int bitcoinconsensus_verify_script(const unsigned char *scriptPubKey, unsigned i
          // Regardless of the verification result, the tx did not error.
          set_error(err, bitcoinconsensus_ERR_OK);
 
-        return VerifyScript(tx.vin[nIn].scriptSig, CScript(scriptPubKey, scriptPubKey + scriptPubKeyLen), flags, TransactionSignatureChecker(&tx, nIn), NULL);
+        return VerifyScript(tx.vin[nIn].scriptSig, CScript(scriptPubKey, scriptPubKey + scriptPubKeyLen), nIn < tx.wit.vtxinwit.size() ? &tx.wit.vtxinwit[nIn].scriptWitness : NULL, flags, TransactionSignatureChecker(&tx, nIn), NULL);
     } catch (const std::exception&) {
         return set_error(err, bitcoinconsensus_ERR_TX_DESERIALIZE); // Error deserializing
     }
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index fd4a5674cf..be649fca20 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -1239,8 +1239,67 @@ bool TransactionSignatureChecker::CheckSequence(const CScriptNum& nSequence) con
     return true;
 }
 
-bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
+static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
 {
+    vector<vector<unsigned char> > stack;
+    CScript scriptPubKey;
+
+    if (witversion == 0) {
+        if (program.size() == 32) {
+            // Version 0 segregated witness program: SHA256(CScript) inside the program, CScript + inputs in witness
+            if (witness.stack.size() == 0) {
+                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY);
+            }
+            scriptPubKey = CScript(witness.stack.back().begin(), witness.stack.back().end());
+            stack = std::vector<std::vector<unsigned char> >(witness.stack.begin(), witness.stack.end() - 1);
+            uint256 hashScriptPubKey;
+            CSHA256().Write(&scriptPubKey[0], scriptPubKey.size()).Finalize(hashScriptPubKey.begin());
+            if (memcmp(hashScriptPubKey.begin(), &program[0], 32)) {
+                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
+            }
+        } else if (program.size() == 20) {
+            // Special case for pay-to-pubkeyhash; signature + pubkey in witness
+            if (witness.stack.size() != 2) {
+                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); // 2 items in witness
+            }
+            scriptPubKey << OP_DUP << OP_HASH160 << program << OP_EQUALVERIFY << OP_CHECKSIG;
+            stack = witness.stack;
+        } else {
+            return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH);
+        }
+    } else if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) {
+        return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM);
+    } else {
+        // Higher version witness scripts return true for future softfork compatibility
+        return set_success(serror);
+    }
+
+    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
+    for (unsigned int i = 0; i < stack.size(); i++) {
+        if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE)
+            return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
+    }
+
+    if (!EvalScript(stack, scriptPubKey, flags, checker, serror)) {
+        return false;
+    }
+
+    // Scripts inside witness implicitly require cleanstack behaviour
+    if (stack.size() != 1)
+        return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
+    if (!CastToBool(stack.back()))
+        return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
+    return true;
+}
+
+bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
+{
+    static const CScriptWitness emptyWitness;
+    if (witness == NULL) {
+        witness = &emptyWitness;
+    }
+    bool hadWitness = false;
+
     set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR);
 
     if ((flags & SCRIPT_VERIFY_SIGPUSHONLY) != 0 && !scriptSig.IsPushOnly()) {
@@ -1261,6 +1320,25 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, unsigne
     if (CastToBool(stack.back()) == false)
         return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
 
+    // Bare witness programs
+    int witnessversion;
+    std::vector<unsigned char> witnessprogram;
+    if (flags & SCRIPT_VERIFY_WITNESS) {
+        if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
+            hadWitness = true;
+            if (scriptSig.size() != 0) {
+                // The scriptSig must be _exactly_ CScript(), otherwise we reintroduce malleability.
+                return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED);
+            }
+            if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) {
+                return false;
+            }
+            // Bypass the cleanstack check at the end. The actual stack is obviously not clean
+            // for witness programs.
+            stack.resize(1);
+        }
+    }
+
     // Additional validation for spend-to-script-hash transactions:
     if ((flags & SCRIPT_VERIFY_P2SH) && scriptPubKey.IsPayToScriptHash())
     {
@@ -1287,19 +1365,48 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, unsigne
             return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
         if (!CastToBool(stack.back()))
             return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
+
+        // P2SH witness program
+        if (flags & SCRIPT_VERIFY_WITNESS) {
+            if (pubKey2.IsWitnessProgram(witnessversion, witnessprogram)) {
+                hadWitness = true;
+                if (scriptSig != CScript() << std::vector<unsigned char>(pubKey2.begin(), pubKey2.end())) {
+                    // The scriptSig must be _exactly_ a single push of the redeemScript. Otherwise we
+                    // reintroduce malleability.
+                    return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED_P2SH);
+                }
+                if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) {
+                    return false;
+                }
+                // Bypass the cleanstack check at the end. The actual stack is obviously not clean
+                // for witness programs.
+                stack.resize(1);
+            }
+        }
     }
 
     // The CLEANSTACK check is only performed after potential P2SH evaluation,
     // as the non-P2SH evaluation of a P2SH script will obviously not result in
-    // a clean stack (the P2SH inputs remain).
+    // a clean stack (the P2SH inputs remain). The same holds for witness evaluation.
     if ((flags & SCRIPT_VERIFY_CLEANSTACK) != 0) {
         // Disallow CLEANSTACK without P2SH, as otherwise a switch CLEANSTACK->P2SH+CLEANSTACK
         // would be possible, which is not a softfork (and P2SH should be one).
         assert((flags & SCRIPT_VERIFY_P2SH) != 0);
+        assert((flags & SCRIPT_VERIFY_WITNESS) != 0);
         if (stack.size() != 1) {
             return set_error(serror, SCRIPT_ERR_CLEANSTACK);
         }
     }
 
+    if (flags & SCRIPT_VERIFY_WITNESS) {
+        // We can't check for correct unexpected witness data if P2SH was off, so require
+        // that WITNESS implies P2SH. Otherwise, going from WITNESS->P2SH+WITNESS would be
+        // possible, which is not a softfork.
+        assert((flags & SCRIPT_VERIFY_P2SH) != 0);
+        if (!hadWitness && !witness->IsNull()) {
+            return set_error(serror, SCRIPT_ERR_WITNESS_UNEXPECTED);
+        }
+    }
+
     return set_success(serror);
 }
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index e5cb7290f2..d1459ed620 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -74,7 +74,7 @@ enum
     // "At least one stack element must remain, and when interpreted as a boolean, it must be true" to
     // "Exactly one stack element must remain, and when interpreted as a boolean, it must be true".
     // (softfork safe, BIP62 rule 6)
-    // Note: CLEANSTACK should never be used without P2SH.
+    // Note: CLEANSTACK should never be used without P2SH or WITNESS.
     SCRIPT_VERIFY_CLEANSTACK = (1U << 8),
 
     // Verify CHECKLOCKTIMEVERIFY
@@ -86,6 +86,14 @@ enum
     //
     // See BIP112 for details
     SCRIPT_VERIFY_CHECKSEQUENCEVERIFY = (1U << 10),
+
+    // Support segregated witness
+    //
+    SCRIPT_VERIFY_WITNESS = (1U << 11),
+
+    // Making v1-v16 witness program non-standard
+    //
+    SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM = (1U << 12),
 };
 
 bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror);
@@ -139,6 +147,6 @@ public:
 };
 
 bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* error = NULL);
-bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* error = NULL);
+bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror = NULL);
 
 #endif // BITCOIN_SCRIPT_INTERPRETER_H
diff --git a/src/script/script.cpp b/src/script/script.cpp
index 6b1eb52bbf..73f5a61bf6 100644
--- a/src/script/script.cpp
+++ b/src/script/script.cpp
@@ -210,6 +210,24 @@ bool CScript::IsPayToScriptHash() const
             (*this)[22] == OP_EQUAL);
 }
 
+// A witness program is any valid CScript that consists of a 1-byte push opcode
+// followed by a data push between 2 and 40 bytes.
+bool CScript::IsWitnessProgram(int& version, std::vector<unsigned char>& program) const
+{
+    if (this->size() < 4 || this->size() > 42) {
+        return false;
+    }
+    if ((*this)[0] != OP_0 && ((*this)[0] < OP_1 || (*this)[0] > OP_16)) {
+        return false;
+    }
+    if ((size_t)((*this)[1] + 2) == this->size()) {
+        version = DecodeOP_N((opcodetype)(*this)[0]);
+        program = std::vector<unsigned char>(this->begin() + 2, this->end());
+        return true;
+    }
+    return false;
+}
+
 bool CScript::IsPushOnly(const_iterator pc) const
 {
     while (pc < end())
diff --git a/src/script/script.h b/src/script/script.h
index 0b6d822d81..b9b5be9013 100644
--- a/src/script/script.h
+++ b/src/script/script.h
@@ -621,6 +621,7 @@ public:
     unsigned int GetSigOpCount(const CScript& scriptSig) const;
 
     bool IsPayToScriptHash() const;
+    bool IsWitnessProgram(int& version, std::vector<unsigned char>& program) const;
 
     /** Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical). */
     bool IsPushOnly(const_iterator pc) const;
diff --git a/src/script/script_error.cpp b/src/script/script_error.cpp
index f1aa1fb408..cef807edcf 100644
--- a/src/script/script_error.cpp
+++ b/src/script/script_error.cpp
@@ -65,8 +65,22 @@ const char* ScriptErrorString(const ScriptError serror)
             return "Dummy CHECKMULTISIG argument must be zero";
         case SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS:
             return "NOPx reserved for soft-fork upgrades";
+        case SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM:
+            return "Witness version reserved for soft-fork upgrades";
         case SCRIPT_ERR_PUBKEYTYPE:
             return "Public key is neither compressed or uncompressed";
+        case SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH:
+            return "Witness program has incorrect length";
+        case SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY:
+            return "Witness program was passed an empty witness";
+        case SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH:
+            return "Witness program hash mismatch";
+        case SCRIPT_ERR_WITNESS_MALLEATED:
+            return "Witness requires empty scriptSig";
+        case SCRIPT_ERR_WITNESS_MALLEATED_P2SH:
+            return "Witness requires only-redeemscript scriptSig";
+        case SCRIPT_ERR_WITNESS_UNEXPECTED:
+            return "Witness provided for non-witness script";
         case SCRIPT_ERR_UNKNOWN_ERROR:
         case SCRIPT_ERR_ERROR_COUNT:
         default: break;
diff --git a/src/script/script_error.h b/src/script/script_error.h
index 26df33932f..09dc6945ad 100644
--- a/src/script/script_error.h
+++ b/src/script/script_error.h
@@ -51,6 +51,15 @@ typedef enum ScriptError_t
 
     /* softfork safeness */
     SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS,
+    SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM,
+
+    /* segregated witness */
+    SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH,
+    SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY,
+    SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH,
+    SCRIPT_ERR_WITNESS_MALLEATED,
+    SCRIPT_ERR_WITNESS_MALLEATED_P2SH,
+    SCRIPT_ERR_WITNESS_UNEXPECTED,
 
     SCRIPT_ERR_ERROR_COUNT
 } ScriptError;
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 2f4111f786..37b702de17 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -123,7 +123,7 @@ bool ProduceSignature(const BaseSignatureCreator& creator, const CScript& fromPu
     }
 
     // Test solution
-    return VerifyScript(scriptSig, fromPubKey, STANDARD_SCRIPT_VERIFY_FLAGS, creator.Checker());
+    return VerifyScript(scriptSig, fromPubKey, NULL, STANDARD_SCRIPT_VERIFY_FLAGS, creator.Checker());
 }
 
 bool SignSignature(const CKeyStore &keystore, const CScript& fromPubKey, CMutableTransaction& txTo, unsigned int nIn, int nHashType)