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