Merge #19953: Implement BIP 340-342 validation (Schnorr/taproot/tapscript)

0e2a5e448f426219a6464b9aaadcc715534114e6 tests: dumping and minimizing of script assets data (Pieter Wuille)
4567ba034c5ae6e6cc161360f7425c9e844738f0 tests: add generic qa-asset-based script verification unit test (Pieter Wuille)
f06e6d03452cf5e0b1a0863afb08c9e6d3ef452e tests: functional tests for Schnorr/Taproot/Tapscript (Pieter Wuille)
3c226639eb134314a0640d34e4ccb6148dbde22f tests: add BIP340 Schnorr signature support to test framework (Pieter Wuille)
206fb180ec6ee5f916afc6f574000d716daf79b7 --- [TAPROOT] Tests --- (Pieter Wuille)
d7ff237f2996a4c11fdf9399187c2d2b26bf9809 Activate Taproot/Tapscript on regtest (BIP 341, BIP 342) (Pieter Wuille)
e9a021d7e6a454d610a45cb9b3995f0d96a5fbb6 Make Taproot spends standard + policy limits (Pieter Wuille)
865d2c37e2e44678498b7f425b65e01b1e231cde --- [TAPROOT] Regtest activation and policy --- (Pieter Wuille)
72422ce396b8eba7b1a72c171c2f07dae691d1b5 Implement Tapscript script validation rules (BIP 342) (Johnson Lau)
330de894a9a48515d9a473448b6c67adc3d188be Use ScriptExecutionData to pass through annex hash (Pieter Wuille)
8bbed4b7acf4c76eaea8c0e10f3cbf6ba4e53809 Implement Taproot validation (BIP 341) (Pieter Wuille)
0664f5fe1f77f08d235aa3750b59428257b0b91d Support for Schnorr signatures and integration in SignatureCheckers (BIP 340) (Pieter Wuille)
5de246ca8159dcffaa4c136a60c8bfed2028e2ee Implement Taproot signature hashing (BIP 341) (Johnson Lau)
9eb590894f15ff40806039bfd32972fbc260e30d Add TaggedHash function (BIP 340) (Pieter Wuille)
450d2b23710ad296eede81339195376021ab5500 --- [TAPROOT] BIP340/341/342 consensus rules --- (Pieter Wuille)
5d62e3a68b6ea9bb03556ee1fbf5678f20be01a2 refactor: keep spent outputs in PrecomputedTransactionData (Pieter Wuille)
8bd2b4e78452ff69c08c37acf164a6b80e503f13 refactor: rename scriptPubKey in VerifyWitnessProgram to exec_script (Pieter Wuille)
107b57df9fa8b2d625d2b342dc77722282a6ae4c scripted-diff: put ECDSA in name of signature functions (Pieter Wuille)
f8c099e2207c90d758e7a659d6a55fa7ccb7ceaa --- [TAPROOT] Refactors --- (Pieter Wuille)

Pull request description:

  This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs [340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), [341](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), and [342](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).

  See the list of commits [below](https://github.com/bitcoin/bitcoin/pull/19953#issuecomment-691815830). No signing or wallet support of any kind is included, as testing is done entirely through the Python test framework.

  This is a successor to https://github.com/bitcoin/bitcoin/pull/17977 (see discussion following [this comment](https://github.com/bitcoin/bitcoin/pull/17977#issuecomment-682285983)), and will have further changes squashed/rebased. The history of this PR can be found in #19997.

ACKs for top commit:
  instagibbs:
    reACK https://github.com/bitcoin/bitcoin/pull/19953/commits/0e2a5e448f426219a6464b9aaadcc715534114e6
  benthecarman:
    reACK 0e2a5e4
  kallewoof:
    reACK 0e2a5e448f426219a6464b9aaadcc715534114e6
  jonasnick:
    ACK 0e2a5e448f426219a6464b9aaadcc715534114e6 almost only looked at bip340/libsecp related code
  jonatack:
    ACK 0e2a5e448f426219a6464b9aaadcc715534114e6 modulo the last four commits (tests) that I plan to finish reviewing tomorrow
  fjahr:
    reACK 0e2a5e448f426219a6464b9aaadcc715534114e6
  achow101:
    ACK 0e2a5e448f426219a6464b9aaadcc715534114e6

Tree-SHA512: 1b00314450a2938a22bccbb4e177230cf08bd365d72055f9d526891f334b364c997e260c10bc19ca78440b6767712c9feea7faad9a1045dd51a5b96f7ca8146e

1 files changed, 91 insertions, 7 deletions

diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index 71f2436369..c0c2b012c6 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -7,14 +7,17 @@
 #define BITCOIN_SCRIPT_INTERPRETER_H
 
 #include <script/script_error.h>
+#include <span.h>
 #include <primitives/transaction.h>
 
 #include <vector>
 #include <stdint.h>
 
 class CPubKey;
+class XOnlyPubKey;
 class CScript;
 class CTransaction;
+class CTxOut;
 class uint256;
 
 /** Signature hash types/flags */
@@ -24,6 +27,10 @@ enum
     SIGHASH_NONE = 2,
     SIGHASH_SINGLE = 3,
     SIGHASH_ANYONECANPAY = 0x80,
+
+    SIGHASH_DEFAULT = 0, //!< Taproot only; implied when sighash byte is missing, and equivalent to SIGHASH_ALL
+    SIGHASH_OUTPUT_MASK = 3,
+    SIGHASH_INPUT_MASK = 0x80,
 };
 
 /** Script verification flags.
@@ -79,6 +86,8 @@ enum
     // "Exactly one stack element must remain, and when interpreted as a boolean, it must be true".
     // (BIP62 rule 6)
     // Note: CLEANSTACK should never be used without P2SH or WITNESS.
+    // Note: WITNESS_V0 and TAPSCRIPT script execution have behavior similar to CLEANSTACK as part of their
+    //       consensus rules. It is automatic there and does not need this flag.
     SCRIPT_VERIFY_CLEANSTACK = (1U << 8),
 
     // Verify CHECKLOCKTIMEVERIFY
@@ -101,6 +110,8 @@ enum
 
     // Segwit script only: Require the argument of OP_IF/NOTIF to be exactly 0x01 or empty vector
     //
+    // Note: TAPSCRIPT script execution has behavior similar to MINIMALIF as part of its consensus
+    //       rules. It is automatic there and does not depend on this flag.
     SCRIPT_VERIFY_MINIMALIF = (1U << 13),
 
     // Signature(s) must be empty vector if a CHECK(MULTI)SIG operation failed
@@ -114,19 +125,49 @@ enum
     // Making OP_CODESEPARATOR and FindAndDelete fail any non-segwit scripts
     //
     SCRIPT_VERIFY_CONST_SCRIPTCODE = (1U << 16),
+
+    // Taproot/Tapscript validation (BIPs 341 & 342)
+    //
+    SCRIPT_VERIFY_TAPROOT = (1U << 17),
+
+    // Making unknown Taproot leaf versions non-standard
+    //
+    SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION = (1U << 18),
+
+    // Making unknown OP_SUCCESS non-standard
+    SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS = (1U << 19),
+
+    // Making unknown public key versions (in BIP 342 scripts) non-standard
+    SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE = (1U << 20),
 };
 
 bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror);
 
 struct PrecomputedTransactionData
 {
+    // BIP341 precomputed data.
+    // These are single-SHA256, see https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-15.
+    uint256 m_prevouts_single_hash;
+    uint256 m_sequences_single_hash;
+    uint256 m_outputs_single_hash;
+    uint256 m_spent_amounts_single_hash;
+    uint256 m_spent_scripts_single_hash;
+    //! Whether the 5 fields above are initialized.
+    bool m_bip341_taproot_ready = false;
+
+    // BIP143 precomputed data (double-SHA256).
     uint256 hashPrevouts, hashSequence, hashOutputs;
-    bool m_ready = false;
+    //! Whether the 3 fields above are initialized.
+    bool m_bip143_segwit_ready = false;
+
+    std::vector<CTxOut> m_spent_outputs;
+    //! Whether m_spent_outputs is initialized.
+    bool m_spent_outputs_ready = false;
 
     PrecomputedTransactionData() = default;
 
     template <class T>
-    void Init(const T& tx);
+    void Init(const T& tx, std::vector<CTxOut>&& spent_outputs);
 
     template <class T>
     explicit PrecomputedTransactionData(const T& tx);
@@ -134,13 +175,48 @@ struct PrecomputedTransactionData
 
 enum class SigVersion
 {
-    BASE = 0,
-    WITNESS_V0 = 1,
+    BASE = 0,        //!< Bare scripts and BIP16 P2SH-wrapped redeemscripts
+    WITNESS_V0 = 1,  //!< Witness v0 (P2WPKH and P2WSH); see BIP 141
+    TAPROOT = 2,     //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, key path spending; see BIP 341
+    TAPSCRIPT = 3,   //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, script path spending, leaf version 0xc0; see BIP 342
+};
+
+struct ScriptExecutionData
+{
+    //! Whether m_tapleaf_hash is initialized.
+    bool m_tapleaf_hash_init = false;
+    //! The tapleaf hash.
+    uint256 m_tapleaf_hash;
+
+    //! Whether m_codeseparator_pos is initialized.
+    bool m_codeseparator_pos_init = false;
+    //! Opcode position of the last executed OP_CODESEPARATOR (or 0xFFFFFFFF if none executed).
+    uint32_t m_codeseparator_pos;
+
+    //! Whether m_annex_present and (when needed) m_annex_hash are initialized.
+    bool m_annex_init = false;
+    //! Whether an annex is present.
+    bool m_annex_present;
+    //! Hash of the annex data.
+    uint256 m_annex_hash;
+
+    //! Whether m_validation_weight_left is initialized.
+    bool m_validation_weight_left_init = false;
+    //! How much validation weight is left (decremented for every successful non-empty signature check).
+    int64_t m_validation_weight_left;
 };
 
 /** Signature hash sizes */
 static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE = 32;
 static constexpr size_t WITNESS_V0_KEYHASH_SIZE = 20;
+static constexpr size_t WITNESS_V1_TAPROOT_SIZE = 32;
+
+static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe;
+static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0;
+static constexpr size_t TAPROOT_CONTROL_BASE_SIZE = 33;
+static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32;
+static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128;
+static constexpr size_t TAPROOT_CONTROL_MAX_SIZE = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT;
 
 template <class T>
 uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache = nullptr);
@@ -148,7 +224,12 @@ uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn
 class BaseSignatureChecker
 {
 public:
-    virtual bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const
+    virtual bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const
+    {
+        return false;
+    }
+
+    virtual bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const
     {
         return false;
     }
@@ -176,12 +257,14 @@ private:
     const PrecomputedTransactionData* txdata;
 
 protected:
-    virtual bool VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const;
+    virtual bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const;
+    virtual bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const;
 
 public:
     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(&txdataIn) {}
-    bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
+    bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
+    bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override;
     bool CheckLockTime(const CScriptNum& nLockTime) const override;
     bool CheckSequence(const CScriptNum& nSequence) const override;
 };
@@ -189,6 +272,7 @@ public:
 using TransactionSignatureChecker = GenericTransactionSignatureChecker<CTransaction>;
 using MutableTransactionSignatureChecker = GenericTransactionSignatureChecker<CMutableTransaction>;
 
+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* error = nullptr);
 bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr);
 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror = nullptr);