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