251};
252
253enum class MiniscriptContext {
254    P2WSH,
255    TAPSCRIPT,
256};
257
258/** Whether the context Tapscript, ensuring the only other possibility is P2WSH. */
259constexpr bool IsTapscript(MiniscriptContext ms_ctx)
260{
261    switch (ms_ctx) {
262        case MiniscriptContext::P2WSH: return false;
263        case MiniscriptContext::TAPSCRIPT: return true;
264    }
265    assert(false);
266}
267
268namespace internal {
269
270//! The maximum size of a witness item for a Miniscript under Tapscript context. (A BIP340 signature with a sighash type byte.)
271inline constexpr uint32_t MAX_TAPMINISCRIPT_STACK_ELEM_SIZE{65};
272
273//! version + nLockTime
274inline constexpr uint32_t TX_OVERHEAD{4 + 4};
275//! prevout + nSequence + scriptSig
276inline constexpr uint32_t TXIN_BYTES_NO_WITNESS{36 + 4 + 1};
277//! nValue + script len + OP_0 + pushdata 32.
278inline constexpr uint32_t P2WSH_TXOUT_BYTES{8 + 1 + 1 + 33};
279//! Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout + segwit marker
280inline constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{(TX_OVERHEAD + GetSizeOfCompactSize(1) + TXIN_BYTES_NO_WITNESS + GetSizeOfCompactSize(1) + P2WSH_TXOUT_BYTES) * WITNESS_SCALE_FACTOR + 2};
281//! Maximum possible stack size to spend a Taproot output (excluding the script itself).
282inline constexpr uint32_t MAX_TAPSCRIPT_SAT_SIZE{GetSizeOfCompactSize(MAX_STACK_SIZE) + (GetSizeOfCompactSize(MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) + MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) * MAX_STACK_SIZE + GetSizeOfCompactSize(TAPROOT_CONTROL_MAX_SIZE) + TAPROOT_CONTROL_MAX_SIZE};
283/** The maximum size of a script depending on the context. */
284constexpr uint32_t MaxScriptSize(MiniscriptContext ms_ctx)
285{
286    if (IsTapscript(ms_ctx)) {
287        // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly
288        // bounded by the maximum standard size of a spending transaction. Let the maximum script
289        // size conservatively be small enough such that even a maximum sized witness and a reasonably
290        // sized spending transaction can spend an output paying to this script without running into
291        // the maximum standard tx size limit.
292        constexpr auto max_size{MAX_STANDARD_TX_WEIGHT - TX_BODY_LEEWAY_WEIGHT - MAX_TAPSCRIPT_SAT_SIZE};
293        return max_size - GetSizeOfCompactSize(max_size);
294    }
295    return MAX_STANDARD_P2WSH_SCRIPT_SIZE;
296}
297
298//! Helper function for Node::CalcType.
299Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
300
301//! Helper function for Node::CalcScriptLen.
302size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
303
304//! A helper sanitizer/checker for the output of CalcType.
305Type SanitizeType(Type x);
306
307//! An object representing a sequence of witness stack elements.
308struct InputStack {
309    /** Whether this stack is valid for its intended purpose (satisfaction or dissatisfaction of a Node).
310     *  The MAYBE value is used for size estimation, when keys/preimages may actually be unavailable,
311     *  but may be available at signing time. This makes the InputStack structure and signing logic,
312     *  filled with dummy signatures/preimages usable for witness size estimation.
313     */
314    Availability available = Availability::YES;
315    //! Whether this stack contains a digital signature.
316    bool has_sig = false;
317    //! Whether this stack is malleable (can be turned into an equally valid other stack by a third party).
318    bool malleable = false;
319    //! Whether this stack is non-canonical (using a construction known to be unnecessary for satisfaction).
320    //! Note that this flag does not affect the satisfaction algorithm; it is only used for sanity checking.
321    bool non_canon = false;
322    //! Serialized witness size.
323    size_t size = 0;
324    //! Data elements.
325    std::vector<std::vector<unsigned char>> stack;
326    //! Construct an empty stack (valid).
327    InputStack() = default;
328    //! Construct a valid single-element stack (with an element up to 75 bytes).
329    InputStack(std::vector<unsigned char> in) : size(in.size() + 1), stack(Vector(std::move(in))) {}
330    //! Change availability
331    InputStack& SetAvailable(Availability avail);
332    //! Mark this input stack as having a signature.
333    InputStack& SetWithSig();
334    //! Mark this input stack as non-canonical (known to not be necessary in non-malleable satisfactions).
335    InputStack& SetNonCanon();
336    //! Mark this input stack as malleable.
337    InputStack& SetMalleable(bool x = true);
338    //! Concatenate two input stacks.
339    friend InputStack operator+(InputStack a, InputStack b);
340    //! Choose between two potential input stacks.
341    friend InputStack operator|(InputStack a, InputStack b);
342};
343
344/** A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in numeric context). */
345inline const auto ZERO = InputStack(std::vector<unsigned char>());
346/** A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challenges). */
347inline const auto ZERO32 = InputStack(std::vector<unsigned char>(32, 0)).SetMalleable();
348/** A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric context). */
349inline const auto ONE = InputStack(Vector((unsigned char)1));
350/** The empty stack. */
351inline const auto EMPTY = InputStack();
352/** A stack representing the lack of any (dis)satisfactions. */
353inline const auto INVALID = InputStack().SetAvailable(Availability::NO);
354
355//! A pair of a satisfaction and a dissatisfaction InputStack.
356struct InputResult {
357    InputStack nsat, sat;
358
359    template<typename A, typename B>
360    InputResult(A&& in_nsat, B&& in_sat) : nsat(std::forward<A>(in_nsat)), sat(std::forward<B>(in_sat)) {}
361};
362
363//! Class whose objects represent the maximum of a list of integers.
364template <typename I>
365class MaxInt
366{
367    bool valid;
368    I value;
369
370public:
371    MaxInt() : valid(false), value(0) {}
372    MaxInt(I val) : valid(true), value(val) {}
373
374    bool Valid() const { return valid; }
375    I Value() const { return value; }
376
377    friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
378        if (!a.valid || !b.valid) return {};
379        return a.value + b.value;
380    }
381
382    friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
383        if (!a.valid) return b;
384        if (!b.valid) return a;
385        return std::max(a.value, b.value);
386    }
387};
388
389struct Ops {
390    //! Non-push opcodes.
391    uint32_t count;
392    //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
393    MaxInt<uint32_t> sat;
394    //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
395    MaxInt<uint32_t> dsat;
396
397    Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
398};
399
400/** A data structure to help the calculation of stack size limits.
401 *
402 * Conceptually, every SatInfo object corresponds to a (possibly empty) set of script execution
403 * traces (sequences of opcodes).
404 * - SatInfo{} corresponds to the empty set.
405 * - SatInfo{n, e} corresponds to a single trace whose net effect is removing n elements from the
406 *   stack (may be negative for a net increase), and reaches a maximum of e stack elements more
407 *   than it ends with.
408 * - operator| is the union operation: (a | b) corresponds to the union of the traces in a and the
409 *   traces in b.
410 * - operator+ is the concatenation operator: (a + b) corresponds to the set of traces formed by
411 *   concatenating any trace in a with any trace in b.
412 *
413 * Its fields are:
414 * - valid is true if the set is non-empty.
415 * - netdiff (if valid) is the largest difference between stack size at the beginning and at the
416 *   end of the script across all traces in the set.
417 * - exec (if valid) is the largest difference between stack size anywhere during execution and at
418 *   the end of the script, across all traces in the set (note that this is not necessarily due
419 *   to the same trace as the one that resulted in the value for netdiff).
420 *
421 * This allows us to build up stack size limits for any script efficiently, by starting from the
422 * individual opcodes miniscripts correspond to, using concatenation to construct scripts, and
423 * using the union operation to choose between execution branches. Since any top-level script
424 * satisfaction ends with a single stack element, we know that for a full script:
425 * - netdiff+1 is the maximal initial stack size (relevant for P2WSH stack limits).
426 * - exec+1 is the maximal stack size reached during execution (relevant for P2TR stack limits).
427 *
428 * Mathematically, SatInfo forms a semiring:
429 * - operator| is the semiring addition operator, with identity SatInfo{}, and which is commutative
430 *   and associative.
431 * - operator+ is the semiring multiplication operator, with identity SatInfo{0}, and which is
432 *   associative.
433 * - operator+ is distributive over operator|, so (a + (b | c)) = (a+b | a+c). This means we do not
434 *   need to actually materialize all possible full execution traces over the whole script (which
435 *   may be exponential in the length of the script); instead we can use the union operation at the
436 *   individual subexpression level, and concatenate the result with subexpressions before and
437 *   after it.
438 * - It is not a commutative semiring, because a+b can differ from b+a. For example, "OP_1 OP_DROP"
439 *   has exec=1, while "OP_DROP OP_1" has exec=0.
440 */
441class SatInfo
442{
443    //! Whether a canonical satisfaction/dissatisfaction is possible at all.
444    bool valid;
445    //! How much higher the stack size at start of execution can be compared to at the end.
446    int32_t netdiff;
447    //! How much higher the stack size can be during execution compared to at the end.
448    int32_t exec;
449
450public:
451    /** Empty script set. */
452    constexpr SatInfo() noexcept : valid(false), netdiff(0), exec(0) {}
453
454    /** Script set with a single script in it, with specified netdiff and exec. */
455    constexpr SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept :
456        valid{true}, netdiff{in_netdiff}, exec{in_exec} {}
457
458    bool Valid() const { return valid; }
459    int32_t NetDiff() const { return netdiff; }
460    int32_t Exec() const { return exec; }
461
462    /** Script set union. */
463    constexpr friend SatInfo operator|(const SatInfo& a, const SatInfo& b) noexcept
464    {
465        // Union with an empty set is itself.
466        if (!a.valid) return b;
467        if (!b.valid) return a;
468        // Otherwise the netdiff and exec of the union is the maximum of the individual values.
469        return {std::max(a.netdiff, b.netdiff), std::max(a.exec, b.exec)};
470    }
471
472    /** Script set concatenation. */
473    constexpr friend SatInfo operator+(const SatInfo& a, const SatInfo& b) noexcept
474    {
475        // Concatenation with an empty set yields an empty set.
476        if (!a.valid || !b.valid) return {};
477        // Otherwise, the maximum stack size difference for the combined scripts is the sum of the
478        // netdiffs, and the maximum stack size difference anywhere is either b.exec (if the
479        // maximum occurred in b) or b.netdiff+a.exec (if the maximum occurred in a).
480        return {a.netdiff + b.netdiff, std::max(b.exec, b.netdiff + a.exec)};
481    }
482
483    /** The empty script. */
484    static constexpr SatInfo Empty() noexcept { return {0, 0}; }
485    /** A script consisting of a single push opcode. */
486    static constexpr SatInfo Push() noexcept { return {-1, 0}; }
487    /** A script consisting of a single hash opcode. */
488    static constexpr SatInfo Hash() noexcept { return {0, 0}; }
489    /** A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY). */
490    static constexpr SatInfo Nop() noexcept { return {0, 0}; }
491    /** A script consisting of just OP_IF or OP_NOTIF. Note that OP_ELSE and OP_ENDIF have no stack effect. */
492    static constexpr SatInfo If() noexcept { return {1, 1}; }
493    /** A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD). */
494    static constexpr SatInfo BinaryOp() noexcept { return {1, 1}; }
495
496    // Scripts for specific individual opcodes.
497    static constexpr SatInfo OP_DUP() noexcept { return {-1, 0}; }
498    static constexpr SatInfo OP_IFDUP(bool nonzero) noexcept { return {nonzero ? -1 : 0, 0}; }
499    static constexpr SatInfo OP_EQUALVERIFY() noexcept { return {2, 2}; }
500    static constexpr SatInfo OP_EQUAL() noexcept { return {1, 1}; }