Inside Bitcoin

501#   - The spent UTXOs by this transaction (list of CTxOut)
502#   - Whether to produce a valid spend (bool)
503# - A string with an expected error message for failure case if known
504# - The (pre-taproot) sigops weight consumed by a successful spend
505# - Whether this spend cannot fail
506# - Whether this test demands being placed in a txin with no corresponding txout (for testing SIGHASH_SINGLE behavior)
507
508Spender = namedtuple("Spender", "script,comment,is_standard,sat_function,err_msg,sigops_weight,no_fail,need_vin_vout_mismatch")
509
510
511def make_spender(comment, *, tap=None, witv0=False, script=None, pkh=None, p2sh=False, spk_mutate_pre_p2sh=None, failure=None, standard=True, err_msg=None, sigops_weight=0, need_vin_vout_mismatch=False, **kwargs):
512    """Helper for constructing Spender objects using the context signing framework.
513
514    * tap: a TaprootInfo object (see taproot_construct), for Taproot spends (cannot be combined with pkh, witv0, or script)
515    * witv0: boolean indicating the use of witness v0 spending (needs one of script or pkh)
516    * script: the actual script executed (for bare/P2WSH/P2SH spending)
517    * pkh: the public key for P2PKH or P2WPKH spending
518    * p2sh: whether the output is P2SH wrapper (this is supported even for Taproot, where it makes the output unencumbered)
519    * spk_mutate_pre_psh: a callable to be applied to the script (before potentially P2SH-wrapping it)
520    * failure: a dict of entries to override in the context when intentionally failing to spend (if None, no_fail will be set)
521    * standard: whether the (valid version of) spending is expected to be standard
522    * err_msg: a string with an expected error message for failure (or None, if not cared about)
523    * sigops_weight: the pre-taproot sigops weight consumed by a successful spend
524    * need_vin_vout_mismatch: whether this test requires being tested in a transaction input that has no corresponding
525                              transaction output.
526    """
527
528    conf = dict()
529
530    # Compute scriptPubKey and set useful defaults based on the inputs.
531    if witv0:
532        assert tap is None
533        conf["mode"] = "witv0"
534        if pkh is not None:
535            # P2WPKH
536            assert script is None
537            pubkeyhash = hash160(pkh)
538            spk = key_to_p2wpkh_script(pkh)
539            conf["scriptcode"] = keyhash_to_p2pkh_script(pubkeyhash)
540            conf["script_witv0"] = None
541            conf["inputs"] = [getter("sign"), pkh]
542        elif script is not None:
543            # P2WSH
544            spk = script_to_p2wsh_script(script)
545            conf["scriptcode"] = script
546            conf["script_witv0"] = script
547        else:
548            assert False
549    elif tap is None:
550        conf["mode"] = "legacy"
551        if pkh is not None:
552            # P2PKH
553            assert script is None
554            pubkeyhash = hash160(pkh)
555            spk = keyhash_to_p2pkh_script(pubkeyhash)
556            conf["scriptcode"] = spk
557            conf["inputs"] = [getter("sign"), pkh]
558        elif script is not None:
559            # bare
560            spk = script
561            conf["scriptcode"] = script
562        else:
563            assert False
564    else:
565        assert script is None
566        conf["mode"] = "taproot"
567        conf["tap"] = tap
568        spk = tap.scriptPubKey
569
570    if spk_mutate_pre_p2sh is not None:
571        spk = spk_mutate_pre_p2sh(spk)
572
573    if p2sh:
574        # P2SH wrapper can be combined with anything else
575        conf["script_p2sh"] = spk
576        spk = script_to_p2sh_script(spk)
577
578    conf = {**conf, **kwargs}
579
580    def sat_fn(tx, idx, utxos, valid):
581        if valid:
582            return spend(tx, idx, utxos, **conf)
583        else:
584            assert failure is not None
585            return spend(tx, idx, utxos, **{**conf, **failure})
586
587    return Spender(script=spk, comment=comment, is_standard=standard, sat_function=sat_fn, err_msg=err_msg, sigops_weight=sigops_weight, no_fail=failure is None, need_vin_vout_mismatch=need_vin_vout_mismatch)
588
589def add_spender(spenders, *args, **kwargs):
590    """Make a spender using make_spender, and add it to spenders."""
591    spenders.append(make_spender(*args, **kwargs))
592
593# === Helpers for the test ===
594
595def random_checksig_style(pubkey):
596    """Creates a random CHECKSIG* tapscript that would succeed with only the valid signature on witness stack."""
597    opcode = random.choice([OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKSIGADD])
598    if opcode == OP_CHECKSIGVERIFY:
599        ret = CScript([pubkey, opcode, OP_1])
600    elif opcode == OP_CHECKSIGADD:
601        num = random.choice([0, 0x7fffffff, -0x7fffffff])
602        ret = CScript([num, pubkey, opcode, num + 1, OP_EQUAL])
603    else:
604        ret = CScript([pubkey, opcode])
605    return bytes(ret)
606
607def bitflipper(expr):
608    """Return a callable that evaluates expr and returns it with a random bitflip."""
609    def fn(ctx):
610        sub = deep_eval(ctx, expr)
611        assert isinstance(sub, bytes)
612        return (int.from_bytes(sub, 'little') ^ (1 << random.randrange(len(sub) * 8))).to_bytes(len(sub), 'little')
613    return fn
614
615def zero_appender(expr):
616    """Return a callable that evaluates expr and returns it with a zero added."""
617    return lambda ctx: deep_eval(ctx, expr) + b"\x00"
618
619def byte_popper(expr):
620    """Return a callable that evaluates expr and returns it with its last byte removed."""
621    return lambda ctx: deep_eval(ctx, expr)[:-1]
622
623# Expected error strings
624
625ERR_SCHNORR_SIG_SIZE = {"err_msg": "Invalid Schnorr signature size"}
626ERR_SCHNORR_SIG_HASHTYPE = {"err_msg": "Invalid Schnorr signature hash type"}
627ERR_SCHNORR_SIG = {"err_msg": "Invalid Schnorr signature"}
628ERR_OP_RETURN = {"err_msg": "OP_RETURN was encountered"}
629ERR_TAPROOT_WRONG_CONTROL_SIZE = {"err_msg": "Invalid Taproot control block size"}
630ERR_WITNESS_PROGRAM_MISMATCH = {"err_msg": "Witness program hash mismatch"}
631ERR_PUSH_SIZE = {"err_msg": "Push value size limit exceeded"}
632ERR_DISABLED_OPCODE = {"err_msg": "Attempted to use a disabled opcode"}
633ERR_TAPSCRIPT_CHECKMULTISIG = {"err_msg": "OP_CHECKMULTISIG(VERIFY) is not available in tapscript"}
634ERR_TAPSCRIPT_MINIMALIF = {"err_msg": "OP_IF/NOTIF argument must be minimal in tapscript"}
635ERR_TAPSCRIPT_EMPTY_PUBKEY = {"err_msg": "Empty public key in tapscript"}
636ERR_STACK_SIZE = {"err_msg": "Stack size limit exceeded"}
637ERR_CLEANSTACK = {"err_msg": "Stack size must be exactly one after execution"}
638ERR_INVALID_STACK_OPERATION = {"err_msg": "Operation not valid with the current stack size"}
639ERR_TAPSCRIPT_VALIDATION_WEIGHT = {"err_msg": "Too much signature validation relative to witness weight"}
640ERR_BAD_OPCODE = {"err_msg": "Opcode missing or not understood"}
641ERR_EVAL_FALSE = {"err_msg": "Script evaluated without error but finished with a false/empty top stack element"}
642ERR_WITNESS_PROGRAM_WITNESS_EMPTY = {"err_msg": "Witness program was passed an empty witness"}
643ERR_CHECKSIGVERIFY = {"err_msg": "Script failed an OP_CHECKSIGVERIFY operation"}
644ERR_SCRIPT_NUM = {"err_msg": "Script number overflowed or is non-minimally encoded"}
645
646VALID_SIGHASHES_ECDSA = [
647    SIGHASH_ALL,
648    SIGHASH_NONE,
649    SIGHASH_SINGLE,
650    SIGHASH_ANYONECANPAY + SIGHASH_ALL,
651    SIGHASH_ANYONECANPAY + SIGHASH_NONE,
652    SIGHASH_ANYONECANPAY + SIGHASH_SINGLE
653]
654
655VALID_SIGHASHES_TAPROOT = [SIGHASH_DEFAULT] + VALID_SIGHASHES_ECDSA
656
657VALID_SIGHASHES_TAPROOT_SINGLE = [
658    SIGHASH_SINGLE,
659    SIGHASH_ANYONECANPAY + SIGHASH_SINGLE
660]
661
662VALID_SIGHASHES_TAPROOT_NO_SINGLE = [h for h in VALID_SIGHASHES_TAPROOT if h not in VALID_SIGHASHES_TAPROOT_SINGLE]
663
664SIGHASH_BITFLIP = {"failure": {"sighash": bitflipper(default_sighash)}}
665SIG_POP_BYTE = {"failure": {"sign": byte_popper(default_sign)}}
666SINGLE_SIG = {"inputs": [getter("sign")]}
667SIG_ADD_ZERO = {"failure": {"sign": zero_appender(default_sign)}}
668
669DUST_LIMIT = 600
670MIN_FEE = 50000
671
672TX_STANDARD_VERSIONS = [1, 2, TX_MAX_STANDARD_VERSION]
673TRUC_MAX_VSIZE = 10000 # test doesn't cover in-mempool spends, so only this limit is hit
674
675# === Actual test cases ===
676
677
678def spenders_taproot_active():
679    """Return a list of Spenders for testing post-Taproot activation behavior."""
680
681    secs = [generate_privkey() for _ in range(8)]
682    pubs = [compute_xonly_pubkey(sec)[0] for sec in secs]
683
684    spenders = []
685
686    # == Tests for BIP340 signature validation. ==
687    # These are primarily tested through the test vectors implemented in libsecp256k1, and in src/tests/key_tests.cpp.
688    # Some things are tested programmatically as well here.
689
690    tap = taproot_construct(pubs[0])
691    # Test with key with bit flipped.
692    add_spender(spenders, "sig/key", tap=tap, key=secs[0], failure={"key_tweaked": bitflipper(default_key_tweaked)}, **ERR_SCHNORR_SIG)
693    # Test with sighash with bit flipped.
694    add_spender(spenders, "sig/sighash", tap=tap, key=secs[0], failure={"sighash": bitflipper(default_sighash)}, **ERR_SCHNORR_SIG)
695    # Test with invalid R sign.
696    add_spender(spenders, "sig/flip_r", tap=tap, key=secs[0], failure={"flag_flip_r": True}, **ERR_SCHNORR_SIG)
697    # Test with invalid P sign.
698    add_spender(spenders, "sig/flip_p", tap=tap, key=secs[0], failure={"flag_flip_p": True}, **ERR_SCHNORR_SIG)
699    # Test with signature with bit flipped.
700    add_spender(spenders, "sig/bitflip", tap=tap, key=secs[0], failure={"signature": bitflipper(default_signature)}, **ERR_SCHNORR_SIG)
701
702    # == Test involving an internal public key not on the curve ==
703
704    # X-only public keys are 32 bytes, but not every 32-byte array is a valid public key; only
705    # around 50% of them are. This does not affect users using correct software; these "keys" have
706    # no corresponding private key, and thus will never appear as output of key
707    # generation/derivation/tweaking.
708    #
709    # Using an invalid public key as P2TR output key makes the UTXO unspendable. Revealing an
710    # invalid public key as internal key in a P2TR script path spend also makes the spend invalid.
711    # These conditions are explicitly spelled out in BIP341.
712    #
713    # It is however hard to create test vectors for this, because it involves "guessing" how a
714    # hypothetical incorrect implementation deals with an obviously-invalid condition, and making
715    # sure that guessed behavior (accepting it in certain condition) doesn't occur.
716    #
717    # The test case added here tries to detect a very specific bug a verifier could have: if they
718    # don't verify whether or not a revealed internal public key in a script path spend is valid,
719    # and (correctly) implement output_key == tweak(internal_key, tweakval) but (incorrectly) treat
720    # tweak(invalid_key, tweakval) as equal the public key corresponding to private key tweakval.
721    # This may seem like a far-fetched edge condition to test for, but in fact, the BIP341 wallet
722    # pseudocode did exactly that (but obviously only triggerable by someone invoking the tweaking
723    # function with an invalid public key, which shouldn't happen).
724
725    # Generate an invalid public key
726    while True:
727        invalid_pub = random.randbytes(32)
728        if not secp256k1.GE.is_valid_x(int.from_bytes(invalid_pub, 'big')):
729            break
730
731    # Implement a test case that detects validation logic which maps invalid public keys to the
732    # point at infinity in the tweaking logic.
733    tap = taproot_construct(invalid_pub, [("true", CScript([OP_1]))], treat_internal_as_infinity=True)
734    add_spender(spenders, "output/invalid_x", tap=tap, key_tweaked=tap.tweak, failure={"leaf": "true", "inputs": []}, **ERR_WITNESS_PROGRAM_MISMATCH)
735
736    # Do the same thing without invalid point, to make sure there is no mistake in the test logic.
737    tap = taproot_construct(pubs[0], [("true", CScript([OP_1]))])
738    add_spender(spenders, "output/invalid_x_mock", tap=tap, key=secs[0], leaf="true", inputs=[])
739
740    # == Tests for signature hashing ==
741
742    # Run all tests once with no annex, and once with a valid random annex.
743    for annex in [None, lambda _: bytes([ANNEX_TAG]) + random.randbytes(random.randrange(0, 250))]:
744        # Non-empty annex is non-standard
745        no_annex = annex is None
746
747        # Sighash mutation tests (test all sighash combinations)
748        for hashtype in VALID_SIGHASHES_TAPROOT:
749            common = {"annex": annex, "hashtype": hashtype, "standard": no_annex}
750