interpreter.h raw
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2022 The Limenka 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 LIMENKA_SCRIPT_INTERPRETER_H
7 #define LIMENKA_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 // Enforce MAX_SCRIPT_ELEMENT_SIZE_REDUCED instead of MAX_SCRIPT_ELEMENT_SIZE
147 // The P2SH redeemScript push is exempted
148 // Taproot control blocks are limited to TAPROOT_CONTROL_MAX_SIZE_REDUCED
149 // Taproot annex is also invalid
150 // OP_IF is also forbidden inside Tapscript
151 SCRIPT_VERIFY_REDUCED_DATA = (1U << 21),
152
153 // P2SPKH witness version 3 validation
154 SCRIPT_VERIFY_P2SPKH = (1U << 22),
155 SCRIPT_VERIFY_P2BPCT = (1U << 23), // witness v4 bulletproof CT validation
156
157 // Constants to point to the highest flag in use. Add new flags above this line.
158 //
159 SCRIPT_VERIFY_END_MARKER
160 };
161
162 static constexpr unsigned int REDUCED_DATA_MANDATORY_VERIFY_FLAGS{0
163 | SCRIPT_VERIFY_REDUCED_DATA
164 | SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM
165 | SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION
166 | SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS
167 };
168
169 bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror);
170
171 struct PrecomputedTransactionData
172 {
173 // BIP341 precomputed data.
174 // These are single-SHA256, see https://github.com/limenka/bips/blob/master/bip-0341.mediawiki#cite_note-16.
175 uint256 m_prevouts_single_hash;
176 uint256 m_sequences_single_hash;
177 uint256 m_outputs_single_hash;
178 uint256 m_spent_amounts_single_hash;
179 uint256 m_spent_scripts_single_hash;
180 //! Whether the 5 fields above are initialized.
181 bool m_bip341_taproot_ready = false;
182
183 // BIP143 precomputed data (double-SHA256).
184 uint256 hashPrevouts, hashSequence, hashOutputs;
185 //! Whether the 3 fields above are initialized.
186 bool m_bip143_segwit_ready = false;
187
188 std::vector<CTxOut> m_spent_outputs;
189 //! Whether m_spent_outputs is initialized.
190 bool m_spent_outputs_ready = false;
191
192 PrecomputedTransactionData() = default;
193
194 /** Initialize this PrecomputedTransactionData with transaction data.
195 *
196 * @param[in] tx The transaction for which data is being precomputed.
197 * @param[in] spent_outputs The CTxOuts being spent, one for each tx.vin, in order.
198 * @param[in] force Whether to precompute data for all optional features,
199 * regardless of what is in the inputs (used at signing
200 * time, when the inputs aren't filled in yet). */
201 template <class T>
202 void Init(const T& tx, std::vector<CTxOut>&& spent_outputs, bool force = false);
203
204 template <class T>
205 explicit PrecomputedTransactionData(const T& tx);
206 };
207
208 enum class SigVersion
209 {
210 BASE = 0, //!< Bare scripts and BIP16 P2SH-wrapped redeemscripts
211 WITNESS_V0 = 1, //!< Witness v0 (P2WPKH and P2WSH); see BIP 141
212 TAPROOT = 2, //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, key path spending; see BIP 341
213 TAPSCRIPT = 3, //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, script path spending, leaf version 0xc0; see BIP 342
214 };
215
216 struct ScriptExecutionData
217 {
218 //! Whether m_tapleaf_hash is initialized.
219 bool m_tapleaf_hash_init = false;
220 //! The tapleaf hash.
221 uint256 m_tapleaf_hash;
222
223 //! Whether m_codeseparator_pos is initialized.
224 bool m_codeseparator_pos_init = false;
225 //! Opcode position of the last executed OP_CODESEPARATOR (or 0xFFFFFFFF if none executed).
226 uint32_t m_codeseparator_pos;
227
228 //! Whether m_annex_present and (when needed) m_annex_hash are initialized.
229 bool m_annex_init = false;
230 //! Whether an annex is present.
231 bool m_annex_present;
232 //! Hash of the annex data.
233 uint256 m_annex_hash;
234
235 //! Whether m_validation_weight_left is initialized.
236 bool m_validation_weight_left_init = false;
237 //! How much validation weight is left (decremented for every successful non-empty signature check).
238 int64_t m_validation_weight_left;
239
240 //! The hash of the corresponding output
241 std::optional<uint256> m_output_hash;
242 };
243
244 /** Signature hash sizes */
245 static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE = 32;
246 static constexpr size_t WITNESS_V0_KEYHASH_SIZE = 20;
247 static constexpr size_t WITNESS_V1_TAPROOT_SIZE = 32;
248 static constexpr size_t WITNESS_V3_SPKHASH_SIZE = 32;
249 static constexpr size_t WITNESS_V4_BPCT_SIZE = 33;
250
251 static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe;
252 static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0;
253 static constexpr size_t TAPROOT_CONTROL_BASE_SIZE = 33;
254 static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32;
255 static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128;
256 static constexpr size_t TAPROOT_CONTROL_MAX_SIZE = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT;
257 static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT_REDUCED = 7;
258 static constexpr size_t TAPROOT_CONTROL_MAX_SIZE_REDUCED = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT_REDUCED;
259
260 extern const HashWriter HASHER_TAPSIGHASH; //!< Hasher with tag "TapSighash" pre-fed to it.
261 extern const HashWriter HASHER_TAPLEAF; //!< Hasher with tag "TapLeaf" pre-fed to it.
262 extern const HashWriter HASHER_TAPBRANCH; //!< Hasher with tag "TapBranch" pre-fed to it.
263
264 /** Data structure to cache SHA256 midstates for the ECDSA sighash calculations
265 * (bare, P2SH, P2WPKH, P2WSH). */
266 class SigHashCache
267 {
268 /** For each sighash mode (ALL, SINGLE, NONE, ALL|ANYONE, SINGLE|ANYONE, NONE|ANYONE),
269 * optionally store a scriptCode which the hash is for, plus a midstate for the SHA256
270 * computation just before adding the hash_type itself. */
271 std::optional<std::pair<CScript, HashWriter>> m_cache_entries[6];
272
273 /** Given a hash_type, find which of the 6 cache entries is to be used. */
274 int CacheIndex(int32_t hash_type) const noexcept;
275
276 public:
277 /** Load into writer the SHA256 midstate if found in this cache. */
278 [[nodiscard]] bool Load(int32_t hash_type, const CScript& script_code, HashWriter& writer) const noexcept;
279 /** Store into this cache object the provided SHA256 midstate. */
280 void Store(int32_t hash_type, const CScript& script_code, const HashWriter& writer) noexcept;
281 };
282
283 template <class T>
284 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);
285
286 class BaseSignatureChecker
287 {
288 public:
289 virtual bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const
290 {
291 return false;
292 }
293
294 virtual bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const
295 {
296 return false;
297 }
298
299 virtual bool CheckLockTime(const CScriptNum& nLockTime) const
300 {
301 return false;
302 }
303
304 virtual bool CheckSequence(const CScriptNum& nSequence) const
305 {
306 return false;
307 }
308
309 virtual ~BaseSignatureChecker() = default;
310 };
311
312 /** Enum to specify what *TransactionSignatureChecker's behavior should be
313 * when dealing with missing transaction data.
314 */
315 enum class MissingDataBehavior
316 {
317 ASSERT_FAIL, //!< Abort execution through assertion failure (for consensus code)
318 FAIL, //!< Just act as if the signature was invalid
319 };
320
321 template<typename T>
322 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);
323
324 template <class T>
325 class GenericTransactionSignatureChecker : public BaseSignatureChecker
326 {
327 private:
328 const T* txTo;
329 const MissingDataBehavior m_mdb;
330 unsigned int nIn;
331 const CAmount amount;
332 const PrecomputedTransactionData* txdata;
333 mutable SigHashCache m_sighash_cache;
334
335 protected:
336 virtual bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const;
337 virtual bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const;
338
339 public:
340 GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, MissingDataBehavior mdb) : txTo(txToIn), m_mdb(mdb), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
341 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) {}
342 bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
343 bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override;
344 bool CheckLockTime(const CScriptNum& nLockTime) const override;
345 bool CheckSequence(const CScriptNum& nSequence) const override;
346
347 bool m_require_sighash_all{false};
348 };
349
350 using TransactionSignatureChecker = GenericTransactionSignatureChecker<CTransaction>;
351 using MutableTransactionSignatureChecker = GenericTransactionSignatureChecker<CMutableTransaction>;
352
353 class DeferringSignatureChecker : public BaseSignatureChecker
354 {
355 protected:
356 const BaseSignatureChecker& m_checker;
357
358 public:
359 DeferringSignatureChecker(const BaseSignatureChecker& checker) : m_checker(checker) {}
360
361 bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override
362 {
363 return m_checker.CheckECDSASignature(scriptSig, vchPubKey, scriptCode, sigversion);
364 }
365
366 bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override
367 {
368 return m_checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror);
369 }
370
371 bool CheckLockTime(const CScriptNum& nLockTime) const override
372 {
373 return m_checker.CheckLockTime(nLockTime);
374 }
375 bool CheckSequence(const CScriptNum& nSequence) const override
376 {
377 return m_checker.CheckSequence(nSequence);
378 }
379 };
380
381 /** Compute the BIP341 tapleaf hash from leaf version & script. */
382 uint256 ComputeTapleafHash(uint8_t leaf_version, Span<const unsigned char> script);
383 /** Compute the BIP341 tapbranch hash from two branches.
384 * Spans must be 32 bytes each. */
385 uint256 ComputeTapbranchHash(Span<const unsigned char> a, Span<const unsigned char> b);
386 /** Compute the BIP341 taproot script tree Merkle root from control block and leaf hash.
387 * Requires control block to have valid length (33 + k*32, with k in {0,1,..,128}). */
388 uint256 ComputeTaprootMerkleRoot(Span<const unsigned char> control, const uint256& tapleaf_hash);
389
390 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);
391 bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr);
392 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror = nullptr);
393
394 size_t CountWitnessSigOps(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags);
395
396 int FindAndDelete(CScript& script, const CScript& b);
397
398 #endif // LIMENKA_SCRIPT_INTERPRETER_H
399