1  // Copyright (c) 2009-2010 Satoshi Nakamoto
  2  // Copyright (c) 2009-present The Bitcoin Core developers
  3  // Distributed under the MIT software license, see the accompanying
  4  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5  
  6  #ifndef BITCOIN_SCRIPT_INTERPRETER_H
  7  #define BITCOIN_SCRIPT_INTERPRETER_H
  8  
  9  #include <consensus/amount.h>
 10  #include <hash.h>
 11  #include <primitives/transaction.h>
 12  #include <script/script_error.h> // IWYU pragma: export
 13  #include <script/verify_flags.h> // IWYU pragma: export
 14  #include <span.h>
 15  #include <uint256.h>
 16  
 17  #include <cstddef>
 18  #include <cstdint>
 19  #include <optional>
 20  #include <vector>
 21  
 22  class CPubKey;
 23  class CScript;
 24  class CScriptNum;
 25  class XOnlyPubKey;
 26  struct CScriptWitness;
 27  
 28  /** Signature hash types/flags */
 29  enum
 30  {
 31      SIGHASH_ALL = 1,
 32      SIGHASH_NONE = 2,
 33      SIGHASH_SINGLE = 3,
 34      SIGHASH_ANYONECANPAY = 0x80,
 35  
 36      SIGHASH_DEFAULT = 0, //!< Taproot only; implied when sighash byte is missing, and equivalent to SIGHASH_ALL
 37      SIGHASH_OUTPUT_MASK = 3,
 38      SIGHASH_INPUT_MASK = 0x80,
 39  };
 40  
 41  /** Script verification flags.
 42   *
 43   *  All flags are intended to be soft forks: the set of acceptable scripts under
 44   *  flags (A | B) is a subset of the acceptable scripts under flag (A).
 45   */
 46  
 47  static constexpr script_verify_flags SCRIPT_VERIFY_NONE{0};
 48  
 49  enum class script_verify_flag_name : uint8_t {
 50      // Evaluate P2SH subscripts (BIP16).
 51      SCRIPT_VERIFY_P2SH,
 52  
 53      // Passing a non-strict-DER signature or one with undefined hashtype to a checksig operation causes script failure.
 54      // Evaluating a pubkey that is not (0x04 + 64 bytes) or (0x02 or 0x03 + 32 bytes) by checksig causes script failure.
 55      // (not used or intended as a consensus rule).
 56      SCRIPT_VERIFY_STRICTENC,
 57  
 58      // Passing a non-strict-DER signature to a checksig operation causes script failure (BIP62 rule 1)
 59      SCRIPT_VERIFY_DERSIG,
 60  
 61      // Passing a non-strict-DER signature or one with S > order/2 to a checksig operation causes script failure
 62      // (BIP62 rule 5).
 63      SCRIPT_VERIFY_LOW_S,
 64  
 65      // verify dummy stack item consumed by CHECKMULTISIG is of zero-length (BIP62 rule 7).
 66      SCRIPT_VERIFY_NULLDUMMY,
 67  
 68      // Using a non-push operator in the scriptSig causes script failure (BIP62 rule 2).
 69      SCRIPT_VERIFY_SIGPUSHONLY,
 70  
 71      // Require minimal encodings for all push operations (OP_0... OP_16, OP_1NEGATE where possible, direct
 72      // pushes up to 75 bytes, OP_PUSHDATA up to 255 bytes, OP_PUSHDATA2 for anything larger). Evaluating
 73      // any other push causes the script to fail (BIP62 rule 3).
 74      // In addition, whenever a stack element is interpreted as a number, it must be of minimal length (BIP62 rule 4).
 75      SCRIPT_VERIFY_MINIMALDATA,
 76  
 77      // Discourage use of NOPs reserved for upgrades (NOP1-10)
 78      //
 79      // Provided so that nodes can avoid accepting or mining transactions
 80      // containing executed NOP's whose meaning may change after a soft-fork,
 81      // thus rendering the script invalid; with this flag set executing
 82      // discouraged NOPs fails the script. This verification flag will never be
 83      // a mandatory flag applied to scripts in a block. NOPs that are not
 84      // executed, e.g.  within an unexecuted IF ENDIF block, are *not* rejected.
 85      // NOPs that have associated forks to give them new meaning (CLTV, CSV)
 86      // are not subject to this rule.
 87      SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS,
 88  
 89      // Require that only a single stack element remains after evaluation. This changes the success criterion from
 90      // "At least one stack element must remain, and when interpreted as a boolean, it must be true" to
 91      // "Exactly one stack element must remain, and when interpreted as a boolean, it must be true".
 92      // (BIP62 rule 6)
 93      // Note: CLEANSTACK should never be used without P2SH or WITNESS.
 94      // Note: WITNESS_V0 and TAPSCRIPT script execution have behavior similar to CLEANSTACK as part of their
 95      //       consensus rules. It is automatic there and does not need this flag.
 96      SCRIPT_VERIFY_CLEANSTACK,
 97  
 98      // Verify CHECKLOCKTIMEVERIFY
 99      //
100      // See BIP65 for details.
101      SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY,
102  
103      // support CHECKSEQUENCEVERIFY opcode
104      //
105      // See BIP112 for details
106      SCRIPT_VERIFY_CHECKSEQUENCEVERIFY,
107  
108      // Support segregated witness
109      //
110      SCRIPT_VERIFY_WITNESS,
111  
112      // Making v1-v16 witness program non-standard
113      //
114      SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM,
115  
116      // Segwit script only: Require the argument of OP_IF/NOTIF to be exactly 0x01 or empty vector
117      //
118      // Note: TAPSCRIPT script execution has behavior similar to MINIMALIF as part of its consensus
119      //       rules. It is automatic there and does not depend on this flag.
120      SCRIPT_VERIFY_MINIMALIF,
121  
122      // Signature(s) must be empty vector if a CHECK(MULTI)SIG operation failed
123      //
124      SCRIPT_VERIFY_NULLFAIL,
125  
126      // Public keys in segregated witness scripts must be compressed
127      //
128      SCRIPT_VERIFY_WITNESS_PUBKEYTYPE,
129  
130      // Making OP_CODESEPARATOR and FindAndDelete fail any non-segwit scripts
131      //
132      SCRIPT_VERIFY_CONST_SCRIPTCODE,
133  
134      // Taproot/Tapscript validation (BIPs 341 & 342)
135      //
136      SCRIPT_VERIFY_TAPROOT,
137  
138      // Making unknown Taproot leaf versions non-standard
139      //
140      SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION,
141  
142      // Making unknown OP_SUCCESS non-standard
143      SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS,
144  
145      // Making unknown public key versions (in BIP 342 scripts) non-standard
146      SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE,
147  
148      // Constants to point to the highest flag in use. Add new flags above this line.
149      //
150      SCRIPT_VERIFY_END_MARKER
151  };
152  using enum script_verify_flag_name;
153  
154  static constexpr int MAX_SCRIPT_VERIFY_FLAGS_BITS = static_cast<int>(SCRIPT_VERIFY_END_MARKER);
155  
156  // assert there is still a spare bit
157  static_assert(0 < MAX_SCRIPT_VERIFY_FLAGS_BITS && MAX_SCRIPT_VERIFY_FLAGS_BITS <= 63);
158  
159  static constexpr script_verify_flags::value_type MAX_SCRIPT_VERIFY_FLAGS = ((script_verify_flags::value_type{1} << MAX_SCRIPT_VERIFY_FLAGS_BITS) - 1);
160  
161  bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, script_verify_flags flags, ScriptError* serror);
162  
163  struct PrecomputedTransactionData
164  {
165      // BIP341 precomputed data.
166      // These are single-SHA256, see https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-16.
167      uint256 m_prevouts_single_hash;
168      uint256 m_sequences_single_hash;
169      uint256 m_outputs_single_hash;
170      uint256 m_spent_amounts_single_hash;
171      uint256 m_spent_scripts_single_hash;
172      //! Whether the 5 fields above are initialized.
173      bool m_bip341_taproot_ready = false;
174  
175      // BIP143 precomputed data (double-SHA256).
176      uint256 hashPrevouts, hashSequence, hashOutputs;
177      //! Whether the 3 fields above are initialized.
178      bool m_bip143_segwit_ready = false;
179  
180      std::vector<CTxOut> m_spent_outputs;
181      //! Whether m_spent_outputs is initialized.
182      bool m_spent_outputs_ready = false;
183  
184      PrecomputedTransactionData() = default;
185  
186      /** Initialize this PrecomputedTransactionData with transaction data.
187       *
188       * @param[in]   tx             The transaction for which data is being precomputed.
189       * @param[in]   spent_outputs  The CTxOuts being spent, one for each tx.vin, in order.
190       * @param[in]   force          Whether to precompute data for all optional features,
191       *                             regardless of what is in the inputs (used at signing
192       *                             time, when the inputs aren't filled in yet). */
193      template <class T>
194      void Init(const T& tx, std::vector<CTxOut>&& spent_outputs, bool force = false);
195  
196      template <class T>
197      explicit PrecomputedTransactionData(const T& tx);
198  };
199  
200  enum class SigVersion
201  {
202      BASE = 0,        //!< Bare scripts and BIP16 P2SH-wrapped redeemscripts
203      WITNESS_V0 = 1,  //!< Witness v0 (P2WPKH and P2WSH); see BIP 141
204      TAPROOT = 2,     //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, key path spending; see BIP 341
205      TAPSCRIPT = 3,   //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, script path spending, leaf version 0xc0; see BIP 342
206  };
207  
208  struct ScriptExecutionData
209  {
210      //! Whether m_tapleaf_hash is initialized.
211      bool m_tapleaf_hash_init = false;
212      //! The tapleaf hash.
213      uint256 m_tapleaf_hash;
214  
215      //! Whether m_codeseparator_pos is initialized.
216      bool m_codeseparator_pos_init = false;
217      //! Opcode position of the last executed OP_CODESEPARATOR (or 0xFFFFFFFF if none executed).
218      uint32_t m_codeseparator_pos;
219  
220      //! Whether m_annex_present and (when needed) m_annex_hash are initialized.
221      bool m_annex_init = false;
222      //! Whether an annex is present.
223      bool m_annex_present;
224      //! Hash of the annex data.
225      uint256 m_annex_hash;
226  
227      //! Whether m_validation_weight_left is initialized.
228      bool m_validation_weight_left_init = false;
229      //! How much validation weight is left (decremented for every successful non-empty signature check).
230      int64_t m_validation_weight_left;
231  
232      //! The hash of the corresponding output
233      std::optional<uint256> m_output_hash;
234  };
235  
236  /** Signature hash sizes */
237  static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE = 32;
238  static constexpr size_t WITNESS_V0_KEYHASH_SIZE = 20;
239  static constexpr size_t WITNESS_V1_TAPROOT_SIZE = 32;
240  
241  static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe;
242  static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0;
243  static constexpr size_t TAPROOT_CONTROL_BASE_SIZE = 33;
244  static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32;
245  static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128;
246  static constexpr size_t TAPROOT_CONTROL_MAX_SIZE = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT;
247  
248  extern const HashWriter HASHER_TAPSIGHASH; //!< Hasher with tag "TapSighash" pre-fed to it.
249  extern const HashWriter HASHER_TAPLEAF;    //!< Hasher with tag "TapLeaf" pre-fed to it.
250  extern const HashWriter HASHER_TAPBRANCH;  //!< Hasher with tag "TapBranch" pre-fed to it.
251  
252  /** Data structure to cache SHA256 midstates for the ECDSA sighash calculations
253   *  (bare, P2SH, P2WPKH, P2WSH). */
254  class SigHashCache
255  {
256      /** For each sighash mode (ALL, SINGLE, NONE, ALL|ANYONE, SINGLE|ANYONE, NONE|ANYONE),
257       *  optionally store a scriptCode which the hash is for, plus a midstate for the SHA256
258       *  computation just before adding the hash_type itself. */
259      std::optional<std::pair<CScript, HashWriter>> m_cache_entries[6];
260  
261      /** Given a hash_type, find which of the 6 cache entries is to be used. */
262      int CacheIndex(int32_t hash_type) const noexcept;
263  
264  public:
265      /** Load into writer the SHA256 midstate if found in this cache. */
266      [[nodiscard]] bool Load(int32_t hash_type, const CScript& script_code, HashWriter& writer) const noexcept;
267      /** Store into this cache object the provided SHA256 midstate. */
268      void Store(int32_t hash_type, const CScript& script_code, const HashWriter& writer) noexcept;
269  };
270  
271  template <class T>
272  uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int32_t nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache = nullptr, SigHashCache* sighash_cache = nullptr);
273  
274  class BaseSignatureChecker
275  {
276  public:
277      virtual bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const
278      {
279          return false;
280      }
281  
282      virtual bool CheckSchnorrSignature(std::span<const unsigned char> sig, std::span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const
283      {
284          return false;
285      }
286  
287      virtual bool CheckLockTime(const CScriptNum& nLockTime) const
288      {
289           return false;
290      }
291  
292      virtual bool CheckSequence(const CScriptNum& nSequence) const
293      {
294           return false;
295      }
296  
297      virtual ~BaseSignatureChecker() = default;
298  };
299  
300  /** Enum to specify what *TransactionSignatureChecker's behavior should be
301   *  when dealing with missing transaction data.
302   */
303  enum class MissingDataBehavior
304  {
305      ASSERT_FAIL,  //!< Abort execution through assertion failure (for consensus code)
306      FAIL,         //!< Just act as if the signature was invalid
307  };
308  
309  template<typename T>
310  bool SignatureHashSchnorr(uint256& hash_out, ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache, MissingDataBehavior mdb);
311  
312  template <class T>
313  class GenericTransactionSignatureChecker : public BaseSignatureChecker
314  {
315  private:
316      const T* txTo;
317      const MissingDataBehavior m_mdb;
318      unsigned int nIn;
319      const CAmount amount;
320      const PrecomputedTransactionData* txdata;
321      mutable SigHashCache m_sighash_cache;
322  
323  protected:
324      virtual bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const;
325      virtual bool VerifySchnorrSignature(std::span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const;
326  
327  public:
328      GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, MissingDataBehavior mdb) : txTo(txToIn), m_mdb(mdb), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
329      GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn, MissingDataBehavior mdb) : txTo(txToIn), m_mdb(mdb), nIn(nInIn), amount(amountIn), txdata(&txdataIn) {}
330      bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
331      bool CheckSchnorrSignature(std::span<const unsigned char> sig, std::span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override;
332      bool CheckLockTime(const CScriptNum& nLockTime) const override;
333      bool CheckSequence(const CScriptNum& nSequence) const override;
334  };
335  
336  using TransactionSignatureChecker = GenericTransactionSignatureChecker<CTransaction>;
337  using MutableTransactionSignatureChecker = GenericTransactionSignatureChecker<CMutableTransaction>;
338  
339  class DeferringSignatureChecker : public BaseSignatureChecker
340  {
341  protected:
342      const BaseSignatureChecker& m_checker;
343  
344  public:
345      DeferringSignatureChecker(const BaseSignatureChecker& checker) : m_checker(checker) {}
346  
347      bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override
348      {
349          return m_checker.CheckECDSASignature(scriptSig, vchPubKey, scriptCode, sigversion);
350      }
351  
352      bool CheckSchnorrSignature(std::span<const unsigned char> sig, std::span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override
353      {
354          return m_checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror);
355      }
356  
357      bool CheckLockTime(const CScriptNum& nLockTime) const override
358      {
359          return m_checker.CheckLockTime(nLockTime);
360      }
361      bool CheckSequence(const CScriptNum& nSequence) const override
362      {
363          return m_checker.CheckSequence(nSequence);
364      }
365  };
366  
367  /** Compute the BIP341 tapleaf hash from leaf version & script. */
368  uint256 ComputeTapleafHash(uint8_t leaf_version, std::span<const unsigned char> script);
369  /** Compute the BIP341 tapbranch hash from two branches.
370    * Spans must be 32 bytes each. */
371  uint256 ComputeTapbranchHash(std::span<const unsigned char> a, std::span<const unsigned char> b);
372  /** Compute the BIP341 taproot script tree Merkle root from control block and leaf hash.
373   *  Requires control block to have valid length (33 + k*32, with k in {0,1,..,128}). */
374  uint256 ComputeTaprootMerkleRoot(std::span<const unsigned char> control, const uint256& tapleaf_hash);
375  
376  bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, script_verify_flags flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* error = nullptr);
377  bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, script_verify_flags flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr);
378  bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, script_verify_flags flags, const BaseSignatureChecker& checker, ScriptError* serror = nullptr);
379  
380  size_t CountWitnessSigOps(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness& witness, script_verify_flags flags);
381  
382  int FindAndDelete(CScript& script, const CScript& b);
383  
384  const std::map<std::string, script_verify_flag_name>& ScriptFlagNamesToEnum();
385  
386  std::vector<std::string> GetScriptFlagNames(script_verify_flags flags);
387  
388  #endif // BITCOIN_SCRIPT_INTERPRETER_H